A tight lower bound for randomized synchronous consensus
Ziv Bar‐Joseph, Michael Ben-Or · 1998
We prove tight upper and lower bounds of @(t/J-) on the expected number of rounds needed for randomized synchronous consensus protocols for a fail-stop, full information, dynamic adversary.In particular this proves that some restrictions are needed on the power of the adversary to allow randomized constant expected number of rounds protocols.