Coin-flipping games immune against linear-sized coalitions

Research output: Contribution to journalArticle

28 Scopus citations

Abstract

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
Volume22
Issue number2
DOIs
StatePublished - Jan 1 1993
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this