2025/04/02 by Chattopadhyay, Eshan, Gurumukhani, Mohit, Ringach, Noam +1
#68Q17 #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #Distributed #F.0 #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2504.01856
Random selection, leader election, and collective coin flipping are fundamental tasks in fault-tolerant distributed computing. We study these problems in the full-information model where 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 improved bounds for these problems. We first show that any k-round coin flipping protocol over ℓ players, each player sending one bit per round, can be biased by O(ℓ/log(k)(ℓ)) bad players. We obtain a similar lower bound for leader election. This strengthens prior best bounds [RSZ, SICOMP 2002] of O(ℓ/log(2k-1)(ℓ)) for coin flipping protocols and O(ℓ/log(2k+1)(ℓ)) for leader election protocols. Our result implies that any (1-bit per player) protocol tolerating linear fraction of bad players requires at least log^* ℓ rounds, showing existing protocols [RZ, JCSS 2001; F, FOCS 1999] are near-optimal. We next initiate the study of one-round, (1-bit per player) random selection. We construct a protocol resilient to ℓ / (log ℓ)2 bad players that outputs (log ℓ)2 / (log log ℓ)2 uniform random bits. This implies a one-round leader election protocol resilient to ℓ / (log ℓ)2 bad players, improving the prior best protocol [RZ, JCSS 2001] which was resilient to ℓ / (log ℓ)3 bad players. Our resilience matches that of the best one-round coin flipping protocol by Ajtai & Linial. We also obtain an almost matching lower bound: any protocol outputting (log ℓ)2 / (log log ℓ)2 bits can be corrupted by ℓ (log log ℓ)2 / (log ℓ)2 bad players. To obtain our lower bound, we introduce multi-output influence, an extension of influence of boolean functions to the multi-output setting.