Coin-flipping games immune against linear-sized coalitions (Extended abstract)

Noga Alon; Moni Naor

doi:10.1109/FSCS.1990.89523

Coin-flipping games immune against linear-sized coalitions (Extended abstract)

Noga Alon
, Moni Naor

Research output: Contribution to journal › Conference article › peer-review

6 Scopus citations

Abstract

Perfect information coin-flipping and leaderelection games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. Answering a question of Ben-Or and Linial we prove 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. We show that a random protocol of a certain length has this property and give an explicit construction as well.

Original language	English (US)
Pages (from-to)	46-54
Number of pages	9
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/FSCS.1990.89523
State	Published - 1990
Externally published	Yes
Event	Proceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA Duration: Oct 22 1990 → Oct 24 1990

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/FSCS.1990.89523

Cite this

@article{5621f1eacbfd48859640cd80646dc558,

title = "Coin-flipping games immune against linear-sized coalitions (Extended abstract)",

abstract = "Perfect information coin-flipping and leaderelection games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. Answering a question of Ben-Or and Linial we prove 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. We show that a random protocol of a certain length has this property and give an explicit construction as well.",

author = "Noga Alon and Moni Naor",

note = "Publisher Copyright: {\textcopyright} 1990 IEEE.; Proceedings of the 31st Annual Symposium on Foundations of Computer Science ; Conference date: 22-10-1990 Through 24-10-1990",

year = "1990",

doi = "10.1109/FSCS.1990.89523",

language = "English (US)",

pages = "46--54",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - Coin-flipping games immune against linear-sized coalitions (Extended abstract)

AU - Alon, Noga

AU - Naor, Moni

PY - 1990

Y1 - 1990

N2 - Perfect information coin-flipping and leaderelection games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. Answering a question of Ben-Or and Linial we prove 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. We show that a random protocol of a certain length has this property and give an explicit construction as well.

AB - Perfect information coin-flipping and leaderelection games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. Answering a question of Ben-Or and Linial we prove 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. We show that a random protocol of a certain length has this property and give an explicit construction as well.

UR - https://www.scopus.com/pages/publications/105031775512

UR - https://www.scopus.com/pages/publications/105031775512#tab=citedBy

U2 - 10.1109/FSCS.1990.89523

DO - 10.1109/FSCS.1990.89523

M3 - Conference article

AN - SCOPUS:105031775512

SN - 0272-5428

SP - 46

EP - 54

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings of the 31st Annual Symposium on Foundations of Computer Science

Y2 - 22 October 1990 through 24 October 1990

ER -

Coin-flipping games immune against linear-sized coalitions (Extended abstract)

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this