1 Search Results for "Er, He Yang"

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-dev.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}
}

Refine by Author
1 Aspnes, James
1 Er, He Yang

Refine by Classification
1 Theory of computation → Distributed algorithms

Refine by Keyword
1 consensus
1 max register
1 oblivious adversary
1 shared memory
1 single-writer register

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Er, He Yang"

Consensus with Max Registers

Abstract

Cite as

Thanks for your feedback!

Could not send message