James Aspnes. Faster randomized consensus with an oblivious adversary. Distributed Computing 28(1):21–29, February 2015. (PODC 2012 special issue). An earlier version appeard in 2012 ACM Symposium on Principles of Distributed Computing, July 2012, pp. 1–8.
Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction 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 O(log* n + log(1/ε)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-ε in O(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 O(log* n) expected steps and randomized consensus for up to (log n)O(log log log n) possible input values using ordinary registers in O(log log n) expected steps.
@article{Aspnes2015,
author = {James Aspnes},
title = {Faster randomized consensus with an oblivious adversary},
month = feb,
year = 2015,
journal = {Distributed Computing},
volume = 28,
number = 1,
pages={21--29}
}