Access Restriction

Author Aspnes, James
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1998
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Consensus ♦ Impossibility ♦ Randomization
Abstract We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip. An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to $\textit{t}$ local coin flips. We show that to guarantee at most constant bias, $ω(\textit{t}2)$ local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in $\textit{t},$ $ω(\textit{t}2/log2\textit{t})$ local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any $\textit{t}-resilient$ asynchronous consensus protocol requires $ω(\textit{t}2/log2\textit{t})$ local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1998-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 45
Issue Number 3
Page Count 36
Starting Page 415
Ending Page 450

Open content in new tab

   Open content in new tab
Source: ACM Digital Library