James Aspnes. Randomized consensus in expected O(n²) total work using single-writer registers. Distributed Computing: 25th International Symposium, DISC 2011. Lecture Notes in Computer Science 6950, Springer-Verlag, September 2011, pp. 363–373.
A new weak shared coin protocol yields a randomized wait-free shared-memory consensus protocol that uses an optimal O(n²) expected total work with single-writer registers despite asynchrony and process crashes. Previously, no protocol was known that achieved this bound without using multi-writer registers.
@inproceedings{Aspnes2011, author = {James Aspnes}, title = {Randomized consensus in expected {$O(n^2)$} total work using single-writer registers}, month =sep, year = 2011, booktitle="Distributed Computing: 25th International Symposium, DISC 2011", series="Lecture Notes in Computer Science", volume=6950, publisher="Springer-Verlag", pages={363--373}, }