A topological perspective on distributed network algorithms
From MaRDI portal
Publication:5919043
DOI10.1016/j.tcs.2020.10.012zbMath1464.68438MaRDI QIDQ5919043
Ami Paz, Matthieu Roy, Armando Castañeda, Sergio Rajsbaum, Corentin Travers, Pierre Fraigniaud
Publication date: 15 December 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- New combinatorial topology bounds for renaming: the lower bound
- Defining liveness
- Linear-in-\(\varDelta \) lower bounds in the LOCAL model
- Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
- The topology of look-compute-move robot wait-free algorithms with hard termination
- A characterization of oblivious message adversaries for which consensus is solvable
- On the expressivity of time-varying graphs
- The Heard-Of model: computing in distributed systems with benign faults
- An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems
- Survey of local algorithms
- Distributed computation in dynamic networks
- Coordinated consensus in dynamic networks
- Tight bounds for k -set agreement
- The Complexity of Data Aggregation in Directed Networks
- The topological structure of asynchronous computability
- Local Computation
- Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms
- The Iterated Restricted Immediate Snapshot Model
- Impossibility of distributed consensus with one faulty process
- Locality in Distributed Graph Algorithms
- Algebraic spans
- Distributed Computing: A Locality-Sensitive Approach
- An Improved Distributed Algorithm for Maximal Independent Set
- Fast, Robust, Quantizable Approximate Consensus *
- Bounds on the Step and Namespace Complexity of Renaming
- Network Topology and Fault-Tolerant Consensus
- On the complexity of local distributed graph problems
- Topological Characterization of Consensus under General Message Adversaries
- Tight Bounds for Asymptotic and Approximate Consensus
- Locally-Iterative Distributed (Δ+ 1)
- Why extension-based proofs fail
- An optimal distributed (Δ+1)-coloring algorithm?
- Generalized FLP impossibility result for t-resilient asynchronous computations
- Wait-free k-set agreement is impossible
- The asynchronous computability theorem for t-resilient tasks
- Distributed computability in Byzantine asynchronous systems
- Set consensus using arbitrary objects (preliminary version)
- Distributed (∆+1)-coloring in sublogarithmic rounds
- A lower bound for the distributed Lovász local lemma
- New combinatorial topology bounds for renaming
- A topological perspective on distributed network algorithms
This page was built for publication: A topological perspective on distributed network algorithms