A Topological Perspective on Distributed Network Algorithms
Copyright policy )A Topological Perspective on Distributed Network Algorithms
More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks.
combinatorial topology, FOS: Computer and information sciences, Network design and communication in computer systems, BOUNDS, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorial topology, Distributed systems, Distributed computing, 102031 Theoretische Informatik, distributed computing, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed graph algorithms, Graph theory (including graph drawing) in computer science, 102031 Theoretical computer science, distributed graph algorithms, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed algorithms, Distributed, Parallel, and Cluster Computing (cs.DC)
combinatorial topology, FOS: Computer and information sciences, Network design and communication in computer systems, BOUNDS, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Combinatorial topology, Distributed systems, Distributed computing, 102031 Theoretische Informatik, distributed computing, Computer Science - Distributed, Parallel, and Cluster Computing, Distributed graph algorithms, Graph theory (including graph drawing) in computer science, 102031 Theoretical computer science, distributed graph algorithms, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed algorithms, Distributed, Parallel, and Cluster Computing (cs.DC)
selected citations These citations are derived from selected sources.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).12 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.Top 10% 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
Citations provided by BIP!Popularity provided by BIP!