Abstract A protocol is presented which solves the randomized consensus problem [9] for shared memory. The protocol uses a total of O ( p 2 + 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 ± ϵ 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.