License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.128
URN: urn:nbn:de:0030-drops-125358
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12535/
Fraigniaud, Pierre ;
Paz, Ami
The Topology of Local Computing in Networks
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 read-write registers), or message-passing 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 3-coloring the n-node 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:1--128:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-138-2},
ISSN = {1868-8969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12535},
URN = {urn:nbn:de:0030-drops-125358},
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 |
