Forgive the tangent, but could quantum entanglement one day provide consensus with trivial (if expensive) complexity? E.g., nodes maintain a supply of preentangled particles, observing them at predetermined timestamps, and using that known shared randomness to make decisions?
Edit: ok after that sat there for a while I realized that generating shared pseudorandom bits would be just as effective.