user4070: Bitcointalk member BTCLuke suggested the following six criterion for a P2P Exchange: 
A P2P Distributed Exchange MUST:

Be without any central points of failure, since a government or two WILL be coming after it one day. I suggest a Bitorrent-like software schematic.
Show everyone a very large number of possible trades to choose from, (thousands?) so assets can form a stable price. (e.g. a Bitcoin is going for $120)
Transact trades pretty much INSTANTANEOUSLY, so when you're watching a graph and want to trade at a very specific time you can do so. (This is extremely important for arbitragers and other traders who help keep the price fluctuation down.)
Offer Graphs and APIs for for graphing like MtGox does.
Have three-user (trustless) trading, so a non-interested 3rd party always hosts the trade between the buyer and seller. (And should provide Escrow too!)
Hold and transfer IOUs without the need for trust

Does there exist a whitepaper or open sourced project that has a solution for all six criterion? Furthermore, who in the community has been working on P2P exchanges and what regulations would impact them?

user2467: Check this suggestion from a member of Open Transactions using Bitmessage for trust-less decentralized exchange system
https://bitcointalk.org/index.php?topic=212490.0

user1307: I think the best we have as a P2P exchange is Ripple. Citing their website:

Ripple is a payment system for any currency with support for
  cross-currency transactions. You can use Ripple to send and receive
  money in dollars, euros, yen or Bitcoin without having to do extra
  work for foreign exchange transactions. Now, you can spend and receive
  your Bitcoin as easily as any fiat currency.

So, Ripple can be used as an exchange for different currencies.
However, it does not comply with all the requirements you listed. Let me go over them.

Be without any central points of failure, since a government or two WILL be coming after it one day. I suggest a Bitorrent-like software schematic.
Ripple itself has no central point of failure if their intended network topology is followed. However, for exchanging currencies, Ripple still depends on gateways that do the actual exchange. Still, these gateways need only to be trusted for a limited amount of currency. If you would really want to, you could see them as the trackers in BitTorrent's paradigm.
Show everyone a very large number of possible trades to choose from, (thousands?) so assets can form a stable price. (e.g. a Bitcoin is going for $120)
In Ripple, all trades happen through gateways. So for every gateway you could have an order book. Probably it's more useful if every gateway just shows its current exchange rate and trade volume. For a more detailed market depth, you will probably be referred to the gateway's website.
Transact trades pretty much INSTANTANEOUSLY, so when you're watching a graph and want to trade at a very specific time you can do so. (This is extremely important for arbitragers and other traders who help keep the price fluctuation down.)
As far as I know, things in Ripple itself are instantaneous. Exchange delays will most probably end up being very gateway-specific.
Offer Graphs and APIs for for graphing like MtGox does.
This is an interesting one. I don't think Ripple currently supports exchanges via gateways. But Ripple is really still very immature (the server code isn't even released yet), so it is very much possible that this is coming.
Since most open software tries to make it possible to do the exact same thing via the API as you can do by using the software itself, this will most probably come to the API.
Have three-user (trustless) trading, so a non-interested 3rd party always hosts the trade between the buyer and seller. (And should provide Escrow too!)
Ripple plans to support escrow. Whether that will apply to XRP transactions as well as gateway exchanges is unsure to me.
Hold and transfer IOUs without the need for trust
Since the whole thing Ripple is built upon is trust, I think it just fails this one. It can hold IOU's though, in fact that's basically all it does.

So, I know Ripple is not the ideal solution you were looking for. But still, Ripple is very much about exchange of currencies, so maybe some day it will be suitable as a true P2P-like exchange.
(Also, I'm no Ripple expert. Feel free to correct me if I made a mistake!)

user2995: Decentralized peer to peer exchange of digital currencies to/from fiat currencies will always have the following constraints:

Fiat currencies cannot be encrypted and represented digitally by a decentralized entity/organization/system. Therefore, fiat currencies will always need to be transferred between traders through the banking system or physically using cash.

Peer to peer trades of fiat<=>digital currencies will always depend on trust. A peer to peer exchange protocol could easily ensure that one party would always send the Bitcoins. The transaction can be verified. The protocol could safely hold the Bitcoins until the other party sends the dollar (Decentralized escrow). But the protocol can never confirm the dollar transaction. It can never know for sure that the transaction has occurred. This introduces the below:



Who's going to send first?
I sent the money. No he didn't
Who will this person be that I'll receive a transfer from? Is he a criminal? Are the funds stolen?
What if this person tells his bank that I fraudulently received this payment.
I went to the cash exchange and had to confirm the transaction at gun point

Remember that transactions  within the banking system are monitored, they can be reversed and funds can be frozen.
I have studied all projects aiming to accomplish a peer to peer decentralized exchange:

Dark Exchange
BitcoinX
Ripple - which is actually a payment system that will hypothetically allow trades as well.

I haven't seen a solution for the above mentioned constraints. All of these projects will be bound by them.
Ripple protocol proposes to allow dollars to be represented on the network and allow peer to peer transfer of dollars, therefore enabling btc->dollar trades. However, their model depends on Gateways -the entry/exit points of fiat currencies to the network. Users will still need to trust that these Gateways will actually hold and be able to pay the amount of dollars within the network as/when needed. There is no guarantee that these Gateways will not fraud the network or individuals. Neither is there a guarantee that the governments will not shut them down. (Read the first line here: https://ripple.com/wiki/Gateway_List)
My view on the future of fiat=>dollar exchanges:
First and foremost: The significance of exchanges will diminish as the adoption of Bitcoin grows. The less the need to trade your Bitcoins, the less important exchanges are. I truly believe this.
Are you saying that we not need exchanges? Absolutely not. No matter how much the adoption rate grows, there will always be a need to trade Bitcoins -this will be true for at least our  lifetime. So we need better and more exchanges.
So what's it gonna be? A ton of local options for people to buy/sell Bitcoins and lots of big exchanges that local shops can trade with. You need to remember that currency exchange does not always have to be in continuous double auction format. When you go to an exchange office and buy euros with dollar, they are not actually matching that with another order. They put a safe profit margin on the price and we pay it. See: CoinBase
Overall, I truly hope that I'm proven wrong. But I don't think a peer to peer decentralized exchange can be built.
Important last note: All of the above are true only for fiat to Bitcoin exchanges. A digital to digital currency exchange can be made peer to peer and decentralized given that both allow peer to peer public transfers and both are decentralized. (Ex. Litecoin to Bitcoin)

4070: <p>Bitcointalk member BTCLuke suggested the following six criterion for a P2P Exchange: </p>

<p>A P2P Distributed Exchange MUST:</p>

<ol>
<li>Be without any central points of failure, since a government or two WILL be coming after it one day. I suggest a Bitorrent-like software schematic.</li>
<li>Show everyone a very large number of possible trades to choose from, (thousands?) so assets can form a stable price. (e.g. a Bitcoin is going for $120)</li>
<li>Transact trades pretty much INSTANTANEOUSLY, so when you're watching a graph and want to trade at a very specific time you can do so. (This is extremely important for arbitragers and other traders who help keep the price fluctuation down.)</li>
<li>Offer Graphs and APIs for for graphing like MtGox does.</li>
<li>Have three-user (trustless) trading, so a non-interested 3rd party always hosts the trade between the buyer and seller. (And should provide Escrow too!)</li>
<li>Hold and transfer IOUs without the need for trust</li>
</ol>

<p>Does there exist a whitepaper or open sourced project that has a solution for all six criterion? Furthermore, who in the community has been working on P2P exchanges and what regulations would impact them?</p>
 2467: <p>Check this suggestion from a member of Open Transactions using Bitmessage for trust-less decentralized exchange system</p>

<p><a href="https://bitcointalk.org/index.php?topic=212490.0" rel="nofollow">https://bitcointalk.org/index.php?topic=212490.0</a></p>
 1307: <p>I think the best we have as a P2P exchange is <a href="http://ripple.com" rel="nofollow">Ripple</a>. Citing their website:</p>

<blockquote>
  <p>Ripple is a payment system for any currency with support for
  cross-currency transactions. You can use Ripple to send and receive
  money in dollars, euros, yen or Bitcoin without having to do extra
  work for foreign exchange transactions. Now, you can spend and receive
  your Bitcoin as easily as any fiat currency.</p>
</blockquote>

<p>So, Ripple can be used as an exchange for different currencies.</p>

<p>However, it does not comply with all the requirements you listed. Let me go over them.</p>

<ol>
<li><p><em>Be without any central points of failure, since a government or two WILL be coming after it one day. I suggest a Bitorrent-like software schematic.</em></p>

<p>Ripple itself has no central point of failure if their intended network topology is followed. However, for exchanging currencies, Ripple still depends on <em>gateways</em> that do the actual exchange. Still, these gateways need only to be trusted for a limited amount of currency. If you would really want to, you could see them as the trackers in BitTorrent's paradigm.</p></li>
<li><p><em>Show everyone a very large number of possible trades to choose from, (thousands?) so assets can form a stable price. (e.g. a Bitcoin is going for $120)</em></p>

<p>In Ripple, all trades happen through gateways. So for every gateway you could have an order book. Probably it's more useful if every gateway just shows its current exchange rate and trade volume. For a more detailed market depth, you will probably be referred to the gateway's website.</p></li>
<li><p><em>Transact trades pretty much INSTANTANEOUSLY, so when you're watching a graph and want to trade at a very specific time you can do so. (This is extremely important for arbitragers and other traders who help keep the price fluctuation down.)</em></p>

<p>As far as I know, things in Ripple itself are instantaneous. Exchange delays will most probably end up being very gateway-specific.</p></li>
<li><p><em>Offer Graphs and APIs for for graphing like MtGox does.</em></p>

<p>This is an interesting one. I don't think Ripple <a href="https://ripple.com/wiki/RPC_API" rel="nofollow">currently supports</a> exchanges via gateways. But Ripple is really still very immature (the server code isn't even released yet), so it is very much possible that this is coming.</p>

<p>Since most open software tries to make it possible to do the exact same thing via the API as you can do by using the software itself, this will most probably come to the API.</p></li>
<li><p><em>Have three-user (trustless) trading, so a non-interested 3rd party always hosts the trade between the buyer and seller. (And should provide Escrow too!)</em></p>

<p>Ripple <a href="https://ripple.com/wiki/Manual_escrow" rel="nofollow">plans to support</a> escrow. Whether that will apply to XRP transactions as well as gateway exchanges is unsure to me.</p></li>
<li><p><em>Hold and transfer IOUs without the need for trust</em></p>

<p>Since the whole thing Ripple is built upon is <em>trust</em>, I think it just fails this one. It can hold IOU's though, in fact that's basically all it does.</p></li>
</ol>

<p>So, I know Ripple is not the ideal solution you were looking for. But still, Ripple is very much about exchange of currencies, so maybe some day it will be suitable as a true P2P-like exchange.</p>

<p>(Also, I'm no Ripple expert. Feel free to correct me if I made a mistake!)</p>
 2995: <p>Decentralized peer to peer exchange of digital currencies to/from fiat currencies will always have the following constraints:</p>
<ul>
<li><p>Fiat currencies cannot be encrypted and represented digitally by a decentralized entity/organization/system. Therefore, fiat currencies will always need to be transferred between traders through the banking system or physically using cash.</p>
</li>
<li><p>Peer to peer trades of fiat&lt;=&gt;digital currencies will always depend on trust. A peer to peer exchange protocol could easily ensure that one party would always send the Bitcoins. The transaction can be verified. The protocol could safely hold the Bitcoins until the other party sends the dollar (Decentralized escrow). But the protocol can never confirm the dollar transaction. It can never know for sure that the transaction has occurred. This introduces the below:</p>
</li>
</ul>
<blockquote>
<p>Who's going to send first?</p>
<p>I sent the money. No he didn't</p>
<p>Who will this person be that I'll receive a transfer from? Is he a criminal? Are the funds stolen?</p>
<p>What if this person tells his bank that I fraudulently received this payment.</p>
<p>I went to the cash exchange and had to confirm the transaction at gun point</p>
</blockquote>
<p>Remember that transactions  within the banking system are monitored, they can be reversed and funds can be frozen.</p>
<p>I have studied all projects aiming to accomplish a peer to peer decentralized exchange:</p>
<ul>
<li><a href="https://bitcointalk.org/index.php?topic=26063.80" rel="noreferrer">Dark Exchange</a></li>
<li><a href="http://bitcoinx.org/" rel="noreferrer">BitcoinX</a></li>
<li>Ripple - which is actually a payment system that will hypothetically allow trades as well.</li>
</ul>
<p>I haven't seen a solution for the above mentioned constraints. All of these projects will be bound by them.</p>
<p>Ripple protocol proposes to allow dollars to be represented on the network and allow peer to peer transfer of dollars, therefore enabling btc-&gt;dollar trades. However, their model depends on Gateways -the entry/exit points of fiat currencies to the network. Users will still need to trust that these Gateways will actually hold and be able to pay the amount of dollars within the network as/when needed. There is no guarantee that these Gateways will not fraud the network or individuals. Neither is there a guarantee that the governments will not shut them down. (Read the first line here: <a href="https://ripple.com/wiki/Gateway_List" rel="noreferrer">https://ripple.com/wiki/Gateway_List</a>)</p>
<p>My view on the future of fiat=&gt;dollar exchanges:</p>
<p><strong>First and foremost:</strong> The significance of exchanges will diminish as the adoption of Bitcoin grows. The less the need to trade your Bitcoins, the less important exchanges are. I truly believe this.</p>
<p><strong>Are you saying that we not need exchanges?</strong> Absolutely not. No matter how much the adoption rate grows, there will always be a need to trade Bitcoins -this will be true for at least our  lifetime. So we need better and more exchanges.</p>
<p><strong>So what's it gonna be?</strong> A ton of local options for people to buy/sell Bitcoins and lots of big exchanges that local shops can trade with. You need to remember that currency exchange does not always have to be in continuous double auction format. When you go to an exchange office and buy euros with dollar, they are not actually matching that with another order. They put a safe profit margin on the price and we pay it. See: CoinBase</p>
<p><strong>Overall</strong>, I truly hope that I'm proven wrong. But I don't think a peer to peer decentralized exchange can be built.</p>
<p><strong>Important last note:</strong> All of the above are true only for fiat to Bitcoin exchanges. A digital to digital currency exchange can be made peer to peer and decentralized given that both allow peer to peer public transfers and both are decentralized. (Ex. Litecoin to Bitcoin)</p>
