Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?

Mohammad T. Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski

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…