TIME-EFFICIENT AND SPACE-EFFICIENT RANDOMIZED CONSENSUS

A protocol is presented which solves the randomized consensus problem [9] for shared memory. The protocol uses a total of O(p2 + n) 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 ± ε(lunate) 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. © 1993 Academic Press, Inc.