Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model

DOI10.1137/S0097539700376007zbMath1008.68053MaRDI QIDQ3149888

David Zuckerman, Alexander Russell, Michael E. Saks

Publication date: 29 September 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

leader electioncollective coin-flippingperfect information model

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

A lower bound for adaptively-secure collective coin flipping protocols ⋮ Adaptively Secure Coin-Flipping, Revisited ⋮ Lower bound for scalable Byzantine agreement ⋮ Short paper: On game-theoretically-fair leader election ⋮ \(\log^\ast\)-round game-theoretically-fair leader election ⋮ Polynomial-time targeted attacks on coin tossing for any number of corruptions ⋮ Unnamed Item ⋮ A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols