Coin-flipping games immune against linear-sized coalitions

Noga Alon, Moni Naor

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


Perfect information coin-flipping and leader-election games arise naturally in the study of fault tolerant distributed computing and have considered in many different scenarios. This paper answers a question of Ben-Or and Linial by proving that for every c < 1 there are such games on n players in which no coalition of cn players can influence the outcome with probability greater than some universal constant times c. (Note that this paper actually proves this statement only for all c < 1/3, but since its universal constant is bigger than 3 the above is trivial for c ≥ 1/3.) This paper shows that a random protocol of a certain length has this property and gives an explicit construction as well.

Original languageEnglish (US)
Pages (from-to)403-417
Number of pages15
JournalSIAM Journal on Computing
Issue number2
StatePublished - 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Coin-flipping games immune against linear-sized coalitions'. Together they form a unique fingerprint.

Cite this