2026-07-25T06:45:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11308 2024-03-06T10:47:54Z ddc:004 open_access

Consensus with Max Registers Aspnes, James Er, He Yang consensus max register single-writer register oblivious adversary shared memory 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 Omega(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^2 n) for single-writer registers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James Aspnes and He Yang Er 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.1 urn:nbn:de:0030-drops-113088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.1 eng https://creativecommons.org/licenses/by/3.0/legalcode