Improved Bounds for Coin Flipping, Leader Election, and Random Selection

Random selection is a fundamental task in fault-tolerant distributed computing where processors select a random outcome from some domain. Two special cases of this, leader election (where the processors designate a leader amongst themselves) and collective coin flipping (where the processors agree on a common random bit), have been especially widely studied. We study these problems in the fullinformation model, where processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors. Despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving new lower bounds for coin flipping protocols and both new upper and lower bounds for leader election and random selection protocols.

We first show that any k-round coin flipping protocol, where each of ℓ players sends 1 bit per round, can be biased by O(ℓ/ log (k) (ℓ)) bad players. We obtain the same lower bound (with an additional log (k+1) (ℓ) factor in the numerator) for leader election as well. This strengthens the previous best lower bounds [RSZ, SICOMP 2002], which ruled out coin flipping protocols resilient to O(ℓ/ log (2k-1) (ℓ)) bad players and leader election protocols resilient to O(ℓ/ log (2k+1) (ℓ)) bad players. As a consequence, we establish that any protocol tolerating a linear fraction of corrupt players, while restricting player messages to 1 bit per round, must run for at least log * ℓ -O(1) rounds, improving on the prior best lower bound of 1 2 log * ℓ -log * log * ℓ. We additionally show that the current best protocols that handle a linear number of corrupt players (from [RZ, JCSS 2001], [F, FOCS 1999]) are near optimal in terms of round complexity and communication per player in a round.

We next initiate the study of one-round random selection protocols where each player sends 1 bit in the round. For all m ≥ (log(ℓ)) 2 , we obtain an optimal one-round protocol: We construct a protocol that is resilient to O(ℓ/m) bad players, outputting m uniform random bits. And, we show that any protocol that outputs m uniform random bits can be corrupted using O(ℓ/m) bad players. As far as we are aware, this is the first provably optimal protocol for any task in the full information model.

As a consequence of our construction, we obtain a one-round leader election protocol resilient to ℓ/(log(ℓ)) 2 bad players, improving on the previous best protocol from [RZ, JCSS 2001] that is resilient to only ℓ/(log(ℓ)) 3 bad players and requires players to send many bits. When m = (log(ℓ)) 2 , our resilience parameter matches that of the best one-round coin flipping protocol by Ajtai and Linial, which only outputs one bit. To obtain our lower bound, we introduce and study multi-output influence, a natural extension of the notion of influence of boolean functions to the multi-output setting.