
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. 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. 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 $\textit{local}$ protocol complexes, whose sizes do not depend on the size of the network. As an application of the design of "compact" protocol complexes, we reformulate the celebrated lower bound of $Ω(\log^*n)$ rounds for 3-coloring the $n$-node ring, in the algebraic topology framework.
combinatorial topology, FOS: Computer and information sciences, 2012 ACM Subject Classification Theory of computation → Distributed algorithms Distributed computing, [INFO] Computer Science [cs], Distributed computing, 004, 102031 Theoretische Informatik, Computer Science - Distributed, Parallel, and Cluster Computing, 2012 ACM Subject Classification Theory of computation → Distributed algorithms Distributed computing distributed graph algorithms combinatorial topology, distributed graph algorithms, 102031 Theoretical computer science, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed, Parallel, and Cluster Computing (cs.DC), ddc: ddc:004
combinatorial topology, FOS: Computer and information sciences, 2012 ACM Subject Classification Theory of computation → Distributed algorithms Distributed computing, [INFO] Computer Science [cs], Distributed computing, 004, 102031 Theoretische Informatik, Computer Science - Distributed, Parallel, and Cluster Computing, 2012 ACM Subject Classification Theory of computation → Distributed algorithms Distributed computing distributed graph algorithms combinatorial topology, distributed graph algorithms, 102031 Theoretical computer science, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed, Parallel, and Cluster Computing (cs.DC), ddc: ddc:004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
