How would an atomic exchange of assets be implemented in a blockchain? There are non-Bitcoin blockchains being created at the moment that are used to trade and transfer assets. It is my understanding that on such a block chain there are "tokens" representing assets such as a share in a company or some other security.

Assuming A wants to exchange with B some assets, how would they create a transaction so that the exchange happens atomically?

A non-atomic solution would be to have A transfer the assets he is selling to B first. Then, B transfers the assets he is paying with back.

Multisig transactions do not seem to solve this problem: One of the signers has to sign first (A). He cannot force B to then sign as well. B might abort the transaction or delay it. This is a trust issue and not atomic.

For a concrete example, A might want to trade a certain Namecoin domain name against another name that is owned by B. This is supposed to be trustless and atomic.
The basic idea is that one party makes a payment in such a way that the funds go back to them unless the other party makes the other payment, in which case the other party gets those funds. The other party can then make the payment and claim the output of the first payment.

Here's one possible more detailed sketch:


A and B each generate a private key, determine the corresponding public key, and exchange them.
A and B each sum the public keys and hash them to form a joint address for the transaction.
A and B form two transactions. One sends the funds back to A but has a lock time in the future. The other sends the funds to B if B provides proof of payment of B's funds to A.
They each sign both transactions and the signatures are summed so that both transactions are ready to submit. No additional transactions for the joint address can be signed unless A and B agree.
A sends her funds to the joint address formed in step 2. A knows that she can get her funds back when the lock time expires and that B can only get the funds if she provides proof of payment to A.
B sends the funds to A and submits the proof of payment along with the signed transaction to get A's funds. At this point, the payment is complete.
If B fails to perform step 6, when the lock time expires, A submits the signed return transaction to get her funds back.