Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914514726813696 |
|---|---|
| author | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Servedio, Rocco A. |
| author_facet | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Servedio, Rocco A. |
| contents | 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 $\ell$ players, each player sending one bit per round, can be biased by $O(\ell/\log^{(k)}(\ell))$ bad players. We obtain a similar lower bound for leader election. This strengthens prior best bounds [RSZ, SICOMP 2002] of $O(\ell/\log^{(2k-1)}(\ell))$ for coin flipping protocols and $O(\ell/\log^{(2k+1)}(\ell))$ for leader election protocols. Our result implies that any (1-bit per player) protocol tolerating linear fraction of bad players requires at least $\log^* \ell$ 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. For all $m\ge (\log(\ell))^2$, we obtain an optimal protocol (a first in the full information model for any task): We construct a protocol resilient to $O(\ell / m)$ bad players that outputs $m$ uniform random bits. And, we show that any protocol that outputs $m$ uniform random bits can be corrupted using $O(\ell / m)$ bad players. This also implies a one-round leader election protocol resilient to $\ell / (\log \ell)^2$ bad players, improving the prior best protocol [RZ, JCSS 2001] which was resilient to $\ell / (\log \ell)^3$ bad players. Our resilience matches that of the best one-round coin flipping protocol by Ajtai & Linial. To obtain our lower bound, we introduce multi-output influence, an extension of influence of boolean functions to the multi-output setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01856 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Bounds for Coin Flipping, Leader Election, and Random Selection Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Servedio, Rocco A. Computational Complexity Cryptography and Security Distributed, Parallel, and Cluster Computing 68Q17 F.0 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 $\ell$ players, each player sending one bit per round, can be biased by $O(\ell/\log^{(k)}(\ell))$ bad players. We obtain a similar lower bound for leader election. This strengthens prior best bounds [RSZ, SICOMP 2002] of $O(\ell/\log^{(2k-1)}(\ell))$ for coin flipping protocols and $O(\ell/\log^{(2k+1)}(\ell))$ for leader election protocols. Our result implies that any (1-bit per player) protocol tolerating linear fraction of bad players requires at least $\log^* \ell$ 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. For all $m\ge (\log(\ell))^2$, we obtain an optimal protocol (a first in the full information model for any task): We construct a protocol resilient to $O(\ell / m)$ bad players that outputs $m$ uniform random bits. And, we show that any protocol that outputs $m$ uniform random bits can be corrupted using $O(\ell / m)$ bad players. This also implies a one-round leader election protocol resilient to $\ell / (\log \ell)^2$ bad players, improving the prior best protocol [RZ, JCSS 2001] which was resilient to $\ell / (\log \ell)^3$ bad players. Our resilience matches that of the best one-round coin flipping protocol by Ajtai & Linial. To obtain our lower bound, we introduce multi-output influence, an extension of influence of boolean functions to the multi-output setting. |
| title | Improved Bounds for Coin Flipping, Leader Election, and Random Selection |
| topic | Computational Complexity Cryptography and Security Distributed, Parallel, and Cluster Computing 68Q17 F.0 |
| url | https://arxiv.org/abs/2504.01856 |