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

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

Alexander Russell, David Zuckerman

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

An optimally fair coin toss, Stochastic coalescence in logarithmic time, Lower bound for scalable Byzantine agreement, Extractors from Reed-Muller codes, 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