Abstract
We conduct a systematic study of asynchronous models of distributed computing consisting of identical finitestate devices that cooperate in a network to decide if the network satisfies a given graphtheoretical property. Models discussed in the literature differ in the detection capabilities of the agents residing at the nodes of the network (detecting the set of states of their neighbors, or counting the number of neighbors in each state), the notion of acceptance (acceptance by halting in a particular configuration, or by stable consensus), the notion of step (synchronous move, interleaving, or arbitrary timing), and the fairness assumptions (nonstarving, or stochasticlike). We study the expressive power of the combinations of these features, and show that the initially twenty possible combinations fit into seven equivalence classes. The classification is the consequence of several equiexpressivity results with a clear interpretation. In particular, we show that acceptance by halting configuration only has nontrivial expressive power if it is combined with counting, and that synchronous and interleaving models have the same power as those in which an arbitrary set of nodes can move at the same time. We also identify simple graph properties that distinguish the expressive power of the seven classes.
BibTeX  Entry
@InProceedings{esparza_et_al:LIPIcs:2020:12822,
author = {Javier Esparza and Fabian Reiter},
title = {{A Classification of Weak Asynchronous Models of Distributed Computing}},
booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)},
pages = {10:110:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771603},
ISSN = {18688969},
year = {2020},
volume = {171},
editor = {Igor Konnov and Laura Kov{\'a}cs},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12822},
URN = {urn:nbn:de:0030drops128229},
doi = {10.4230/LIPIcs.CONCUR.2020.10},
annote = {Keywords: Asynchrony, Concurrency theory, Weak models of distributed computing}
}
Keywords: 

Asynchrony, Concurrency theory, Weak models of distributed computing 
Collection: 

31st International Conference on Concurrency Theory (CONCUR 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 