License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2019.34
URN: urn:nbn:de:0030-drops-109365
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10936/
Go to the corresponding LIPIcs Volume Portal


Ledent, Jérémy ; Mimram, Samuel

A Sound Foundation for the Topological Approach to Task Solvability

pdf-format:
LIPIcs-CONCUR-2019-34.pdf (0.5 MB)


Abstract

The area of fault-tolerant distributed computability is concerned with the solvability of decision tasks in various computational models where the processes might crash. A very successful approach to prove impossibility results in this context is that of combinatorial topology, started by Herlihy and Shavit's paper in 1999. They proved that, for wait-free protocols where the processes communicate through read/write registers, a task is solvable if and only if there exists some map between simplicial complexes satisfying some properties. This approach was then extended to many different contexts, where the processes have access to various synchronization and communication primitives. Usually, in those cases, the existence of a simplicial map from the protocol complex to the output complex is taken as the definition of what it means to solve a task. In particular, no proof is provided of the fact that this abstract topological definition agrees with a more concrete operational definition of task solvability. In this paper, we bridge this gap by proving a version of Herlihy and Shavit's theorem that applies to any kind of object. First, we start with a very general way of specifying concurrent objects, and we define what it means to implement an object B in a computational model where the processes are allowed to communicate through shared objects A_1, ..., A_k. Then, we derive the notion of a decision task as a special case of concurrent object. Finally, we prove an analogue of Herlihy and Shavit's theorem in this context. In particular, our version of the theorem subsumes all the uses of the combinatorial topology approach that we are aware of.

BibTeX - Entry

@InProceedings{ledent_et_al:LIPIcs:2019:10936,
  author =	{J{\'e}r{\'e}my Ledent and Samuel Mimram},
  title =	{{A Sound Foundation for the Topological Approach to Task Solvability}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Wan Fokkink and Rob van Glabbeek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10936},
  URN =		{urn:nbn:de:0030-drops-109365},
  doi =		{10.4230/LIPIcs.CONCUR.2019.34},
  annote =	{Keywords: Fault-tolerant protocols, Asynchronous computability, Combinatorial topology, Protocol complex, Distributed task}
}

Keywords: Fault-tolerant protocols, Asynchronous computability, Combinatorial topology, Protocol complex, Distributed task
Seminar: 30th International Conference on Concurrency Theory (CONCUR 2019)
Issue Date: 2019
Date of publication: 26.08.2019


DROPS-Home | Imprint | Privacy Published by LZI