There is already a working (mostly) decentralized exchange: https://bitcointalk.org/index.php?topic=27055.0

It does not use the method described above. I'm not sure how you would implement it. Instead, it works like OTC where you can post your order to the network and others can find it, or you can search for orders already posted.

There is a working implementation, but hardly anyone is using it, and it's having issues with a few exceptions here and there. However, I've used it to exchange coins and so have a few others.