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.
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.