Ledent, Jérémy ;
Mimram, Samuel
A Sound Foundation for the Topological Approach to Task Solvability
Abstract
The area of faulttolerant 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 waitfree 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:134:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771214},
ISSN = {18688969},
year = {2019},
volume = {140},
editor = {Wan Fokkink and Rob van Glabbeek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10936},
URN = {urn:nbn:de:0030drops109365},
doi = {10.4230/LIPIcs.CONCUR.2019.34},
annote = {Keywords: Faulttolerant protocols, Asynchronous computability, Combinatorial topology, Protocol complex, Distributed task}
}
2019
Keywords: 

Faulttolerant protocols, Asynchronous computability, Combinatorial topology, Protocol complex, Distributed task 
Seminar: 

30th International Conference on Concurrency Theory (CONCUR 2019)

Issue date: 

2019 
Date of publication: 

2019 