What is the simplest setting where randomization can help solve consensus? Assume lock-step (synchrony) with $f<n$ crash failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. This lower bound holds even if the protocol is randomized so the natural question is: Can randomization help...
