Randomized consensus in expected O(n²) total work using single-writer registers

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.

Abstract

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.

BibTeX

Download
@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},
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page