For price-discovery you could just use a simple call-market: http://www.investopedia.com/terms/c/callmarket.asp#axzz1Q4BdJydP
and slowly grow that into a continuous market (NASDAQ-like bid-ask matching). I did some research with distributed pub-sub frameworks and DHTs in the past. I find that feasible.
Regulation is going to be a pain. But as long as you keep it simple, you won't have to worry about it. For example if you make all bids final for a period, you may avoid front-running. If you do not allow derivatives being part of the market itself, you also save yourself a lot of trouble there.
Think like the old Mercedes-Diesel Engineers (like the guys pre-1990s not the guys who engineer the junk today): "Everything that is excluded from the design, cannot break."
