James Aspnes and He Yang Er. Consensus with max registers. 32nd International Symposium on Distributed Computing (DISC 2019), October 2019, pp. 1:1–1:19.
We consider the problem of implementing randomized wait-free consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve m-valued consensus for arbitrary m in expected O(log* n) steps per process, beating the Ω(log m / log log m) lower bound for ordinary registers when m is large and the best previously known O(log log n) upper bound when m is small. A simple max-register implementation based on double-collect snapshots translates this result into an O(n log n) expected step implementation of m-valued consensus from n single-writer registers, improving on the best previously-known bound of O(n log² n).
@InProceedings{AspnesE2019,
author ={James Aspnes and He Yang Er},
title ={Consensus with Max Registers},
booktitle ={33rd International Symposium on Distributed Computing ({DISC} 2019)},
pages ={1:1--1:9},
series ={Leibniz International Proceedings in Informatics ({LIPIcs})},
ISBN ={978-3-95977-126-9},
ISSN ={1868-8969},
year ={2019},
volume ={146},
editor ={Jukka Suomela},
publisher ={Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address ={Dagstuhl, Germany},
URL ={https://drops.dagstuhl.de/opus/volltexte/2019/11308},
URN ={urn:nbn:de:0030-drops-113088},
doi ={10.4230/LIPIcs.DISC.2019.1},
annote ={Keywords: consensus, max register, single-writer register, oblivious adversary, shared memory}
}