Abstract
Modeling distributed computing in a way enabling the use of formal methods is a challenge that has been approached from different angles, among which two techniques emerged at the turn of the century: protocol complexes, and directed algebraic topology. In both cases, the considered computational model generally assumes communication via shared objects (typically a shared memory consisting of a collection of readwrite registers), or messagepassing enabling direct communication between any pair of processes. Our paper is concerned with network computing, where the processes are located at the nodes of a network, and communicate by exchanging messages along the edges of that network (only neighboring processes can communicate directly).
Applying the topological approach for verification in network computing is a considerable challenge, mainly because the presence of identifiers assigned to the nodes yields protocol complexes whose size grows exponentially with the size of the underlying network. However, many of the problems studied in this context are of local nature, and their definitions do not depend on the identifiers or on the size of the network. We leverage this independence in order to meet the above challenge, and present local protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compacted" protocol complexes, we reformulate the celebrated lower bound of Ω(log^*n) rounds for 3coloring the nnode ring, in the algebraic topology framework.
BibTeX  Entry
@InProceedings{fraigniaud_et_al:LIPIcs:2020:12535,
author = {Pierre Fraigniaud and Ami Paz},
title = {{The Topology of Local Computing in Networks}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {128:1128:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12535},
URN = {urn:nbn:de:0030drops125358},
doi = {10.4230/LIPIcs.ICALP.2020.128},
annote = {Keywords: Distributed computing, distributed graph algorithms, combinatorial topology}
}
Keywords: 

Distributed computing, distributed graph algorithms, combinatorial topology 
Collection: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) 
Issue Date: 

2020 
Date of publication: 

29.06.2020 