Perfect information leader election in \(\log^*n+O(1)\) rounds

DOI10.1006/jcss.2001.1776zbMath1006.68012OpenAlexW1994659270MaRDI QIDQ1604211

David Zuckerman, Alexander Russell

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1776

zbMATH Keywords

distributed computingleader electioncollective coinflippingcollective sampling

Mathematics Subject Classification ID

Distributed systems (68M14) Network protocols (68M12)

Related Items

Game-theoretic fairness meets multi-party protocols: the case of leader election ⋮ Lower bound for scalable Byzantine agreement ⋮ An optimally fair coin toss ⋮ High entropy random selection protocols ⋮ \(\log^\ast\)-round game-theoretically-fair leader election ⋮ Stochastic coalescence in logarithmic time ⋮ Extractors from Reed-Muller codes ⋮ Unnamed Item ⋮ Explicit two-source extractors and resilient functions ⋮ Rationality in the Full-Information Model ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The influence of large coalitions
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Fast perfect-information leader-election protocols with linear immunity
• Weighted sums of certain dependent random variables
• Simple and efficient leader election in the full information model
• A Robust Noncryptographic Protocol for Collective Coin Flipping
• Coin-Flipping Games Immune against Linear-Sized Coalitions
• An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
• Perfect-Information Leader Election with Optimal Resilience
• Probability Inequalities for Sums of Bounded Random Variables