DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2019.1

Consensus with Max Registers

Authors: James Aspnes and He Yang Er

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract

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.

Cite as

James Aspnes and He Yang Er. Consensus with Max Registers. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aspnes_et_al:LIPIcs.DISC.2019.1,
  author =	{Aspnes, James and Er, He Yang},
  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 =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.1},
  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}
}

Search Results

Documents authored by Er, He Yang

Consensus with Max Registers

Abstract

Cite as

Thanks for your feedback!

Could not send message