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 (n² n) rounds and sends O (n²³ n) communication bits, where the number of faulty parties is (n). Our result is simultaneously tight for both these measures within polylogarithmic factors: due to the (n²) lower bound on communication by Abraham et al. (PODC'19) and (n/ n) lower bound on the number of rounds by Bar-Joseph and Ben-Or (PODC'98). We also quantify how much randomness is necessary and sufficient to reduce time complexity to a certain value, while keeping the communication complexity (nearly) optimal. We prove that no MC algorithm can work in less than (n²\{R, n\ n}) rounds if it uses less than O (R) calls to a random source, assuming a constant fraction of faulty parties. This can be contrasted with a long line of work on consensus against an adversary limited to polynomial computation time, thus unable to break cryptographic primitives, culminating in a work by Ghinea et al. (EUROCRYPT'22), where an optimal O (r) -round solution with probability 1- (cr) ^-r is given. Our lower bound strictly separates these two regimes, by excluding such results if the adversary is computationally unbounded. On the upper bound side, we show that for R (n^3/2) there exists an algorithm solving consensus in O (n²R) rounds with high probability, where tilde notation hides a polylogarithmic factor. The communication complexity of the algorithm does not depend on the amount of randomness R and stays optimal within polylogarithmic factor.