Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of
Randomness is Needed?
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of
Randomness is Needed?
We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. The faulty parties are selected and controlled by an adaptive, full-information, computationally unbounded adversary. We design a randomized algorithm that works in $O(\sqrt{n}\log^2 n)$ …