Faster Randomized Consensus With an Oblivious Adversary

摘要

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new const ruction of a conciliator, an object that guarantees termination and validity, but that: only guarantees agreement: with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-∈ in Ο(log~* n + log(1/∈)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-∈ in Ο(log log n + log(1/∈)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in Ο(log~* n) expected steps and randomized consensus for up to Ο(log n log log n) possible input values using ordinary registers in Ο(log log n) expected steps.