Time-and space-efficient randomized consensus
James Aspnes · 1990
An algorithm is presented which solves the randomized consensus problem [7] for shared memory.The algorithm uses O(p2 + n) worst-case expected 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 thus requires less space than previous polynomial-time consensus protocols [4,6], 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 l/2 f 6 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.