Time- and Space-Efficient Randomized Consensus

✍ Scribed by J. Aspnes

• Book ID: 102968465
• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 751 KB
• Volume: 14
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1993.1022

✦ Synopsis

A protocol is presented which solves the randomized consensus problem [9] for shared memory. The protocol uses a total of (O\left(p^{2}+n\right)) worst-case expected increment, decrement, and read operations on a set of three shared (O(\log n))-bit counters, where (p) is the number of active processors and (n) is the total number of processors. It requires less space than previous polynomial-time consensus protocols [6, 7], and is faster when not all of the processors participate in the protocol. A modified version of the protocol yields a weak shared coin whose bias is guaranteed to be in the range (1 / 2 \pm \epsilon) regardless of scheduler behavior, and which is the first such protocol for the shared-memory model to guarantee that all processors agree on the outcome of the coin. (19493 Academic Press, Inc.