Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why a Lot of Randomness is Needed?
Mohammad Taghi Hajiaghayi, Dariusz Rafal Kowalski, Jan Olkowski · 2024
We study the complexity of the problem of reaching agreement in a synchronous distributed system, also called consensus, 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 [EQUATION] rounds and sends O(n2 log3 n) total number of communication bits, where the number of faulty parties can be Θ(n). When the number of faulty parties is linear in n, our result is simultaneously tight for both these measures within polylogarithmic factors: due to the Ω(n2) lower bound on the number of messages send by any Monte Carlo solution, by Abraham et al. (PODC'19), and due to the [EQUATION] lower bound on the number of rounds of any Las Vegas solution, by Bar-Joseph and Ben-Or (PODC'98). Thereby, this work settles the landscape of the consensus problem in the omission failures model, which stood as an open question since the work of Dolev and Strong (SICOMP'83).