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

DOI10.1006/jcss.2001.1776zbMath1006.68012MaRDI 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 computing; leader election; collective coinflipping; collective sampling

Mathematics Subject Classification ID

68M14: Distributed systems

68M12: Network protocols

Related Items

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

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