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.

Authors

• Armando Castañeda
• Pierre Fraigniaud
• Ami Paz
• Sergio Rajsbaum
• Matthieu Roy
• Corentin Travers

Keywords

• Distributed computing
• Distributed graph algorithms
• Combinatorial topology