I don't think it's that good of an idea. If the allocation is random, participants will counter by sending in more orders than they want, to increase their chance of getting a fill. The microstructure will look similar to a market with a pro-rata matching algo. This article has a good discussion of some of the downsides of pro-rata http://www.advantagefutures.com/is-pro-rata-an-accident-wait....
But it's unclear to me how the random component would work that you all are talking about. Is my resting order subject to a random cancel delay as well? If it's not, then we still have a requirement for speed, as cancelling soon-to-be bad orders is arguably more important than placing soon-to-be good aggressive orders. And if it is subject to a delay, spreads are going to be MUCH wider, losing individual investors more money than they currently are to the current system.
The way I imagined the randomness aspect is the same way it's handled now for two orders received at the same time according to the machine's precision of time perception.
Unfortunately, a loss of efficiency (increased spreads) is the price we will pay for less frequent crashes/spikes.
The El Farol Bar Problem is great reading; thanks for that link.