Brief Announcement: Randomized Consensus: Common Coins Are not the Holy Grail!
Achour Mostéfaoui, Matthieu Perrin, Julien Weibel · 2024
This paper studies the round complexity of randomized binary consensus in crash-prone asynchronous distributed systems. While the Consensus problem cannot be solved deterministically, Ben-Or and Rabin showed that randomization allows solving the problem with probability 1. Moreover, while local coins may need an exponential number of rounds in n, a common coin that delivers the same random sequence to all processes allows termination within a constant mean number of rounds. This paper studies the round complexity and the optimality for different coins. Surprisingly, while the common coin is optimal when t > n/3, it is not when t ≤ n/3.