DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.23

Task Computability in Unreliable Anonymous Networks

Authors: Petr Kuznetsov and Nayuta Yanagisawa

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract

We consider the anonymous broadcast model: a set of n anonymous processes communicate via send-to-all primitives. We assume that underlying communication channels are asynchronous but reliable, and that the processes are subject to crash failures. We show first that in this model, even a single faulty process precludes implementations of atomic objects with non-commuting operations, even as simple as read-write registers or add-only sets. We, however, show that a sequentially consistent read-write memory and add-only sets can be implemented t-resiliently for t<n/2, i.e., provided that a majority of the processes do not fail. We use this implementation to establish an equivalence between the t-resilient read-write anonymous shared-memory model and the t-resilient anonymous broadcast model in terms of colorless task solvability. As a result, we obtain the first task computability characterization for unreliable anonymous message-passing systems.

Cite as

Petr Kuznetsov and Nayuta Yanagisawa. Task Computability in Unreliable Anonymous Networks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2018.23,
  author =	{Kuznetsov, Petr and Yanagisawa, Nayuta},
  title =	{{Task Computability in Unreliable Anonymous Networks}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.23},
  URN =		{urn:nbn:de:0030-drops-100830},
  doi =		{10.4230/LIPIcs.OPODIS.2018.23},
  annote =	{Keywords: Distributed tasks, anonymous broadcast, fault-tolerance}
}

Search Results

Documents authored by Yanagisawa, Nayuta

Task Computability in Unreliable Anonymous Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message