A Topological Perspective on Distributed Network Algorithms - Archive ouverte HAL Access content directly
Conference Papers Theoretical Computer Science Year : 2019

A Topological Perspective on Distributed Network Algorithms

(1) , (2, 3) , (2) , (4) , (5) , (6)
1
2
3
4
5
6

Abstract

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 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.

Dates and versions

hal-02433511 , version 1 (09-01-2020)

Identifiers

Cite

Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, et al.. A Topological Perspective on Distributed Network Algorithms. 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), Jul 2019, L'Aquila, Italy. ⟨10.1007/978-3-030-24922-9_1⟩. ⟨hal-02433511⟩
71 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More