Lower bounds for leader election and collective coin-flipping in the perfect information model

Alexander Russell, Michael Saks, David Zuckerman

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations

Abstract

Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds; we focus on protocols which permit each player to broadcast a single bit per round. We demonstrate that any n-player coin-flipping protocol resilient against corrupt coalitions of linear size must use {1/2 - o(1)} log* n rounds of communication. Such a bound also applies to the leader election problem. This extends work of Kahn, Kalai, and Linial, who proved a similar result for single-round protocols. The primary component of the above result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, we prove a new bound on the influence of sets of variables of size βn, for β>1/3.

Original languageEnglish (US)
Pages (from-to)339-347
Number of pages9
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 31st Annual ACM Symposium on Theory of Computing - FCRC '99 - Atlanta, GA, USA
Duration: May 1 1999May 4 1999

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Lower bounds for leader election and collective coin-flipping in the perfect information model'. Together they form a unique fingerprint.

Cite this