# Wait-free approximate agreement on graphs

@inproceedings{Alistarh2021WaitfreeAA, title={Wait-free approximate agreement on graphs}, author={Dan Alistarh and Faith Ellen and Joel Rybicki}, booktitle={SIROCCO}, year={2021} }

Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that – all the outputs are within distance 1 of one another, and – each output value… Expand

#### 3 Citations

Brief Announcement: Variants of Approximate Agreement on Graphs and Simplicial Complexes

- Computer Science
- PODC
- 2021

This work shows that both tasks of approximate agreement on graphs, edge agreement and clique agreement arise as special cases of a more general, higher-dimensional, approximate agreement task, where the processes must agree on the vertices of a simplex in a given simplicial complex. Expand

Reductions and Extension-Based Proofs

- Computer Science
- PODC
- 2021

It is proved that, if T reduces to S, and T has an augmented extension-based proof that it is impossible to solve in the NIS model, then so does S. Expand

Why extension-based proofs fail

- Computer Science
- STOC
- 2019

This work introduces extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments. Expand

#### References

SHOWING 1-10 OF 58 REFERENCES

Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

- Computer Science, Mathematics
- SIAM J. Comput.
- 2000

It is shown that for any k < n, there is no deterministic wait-free protocol for n processors that solves the k-set agreement problem and this structure reveals a close analogy between the impossibility ofWait-free k- set agreement and the Brouwer fixed point theorem for thek-dimensional ball. Expand

Convergence and covering on graphs for wait-free robots

- Computer Science
- Journal of the Brazilian Computer Society
- 2017

This article studies the case where the space is uni-dimensional, modeled as a graph G, and considers a variant of robot convergence on graphs, edge covering, where additionally, it is required that not all robots end up on the same vertex. Expand

Generalized FLP impossibility result for t-resilient asynchronous computations

- Computer Science
- STOC '93
- 1993

This paper generalizes FLP to multiple faults and establishes that k-set consensus proposed by Chaudhuri is impossible, if the protocol is to tolerate k failures, while there exists a protocol that tolerates k – 1 failures. Expand

The asynchronous computability theorem for t-resilient tasks

- Mathematics, Computer Science
- STOC '93
- 1993

The main theorem characterizes computability y in terms of the topological properties of a simplicial complex so that a given task is computable only if it can be associated with a complex that is simply connected with trivial homology groups. Expand

Byzantine Approximate Agreement on Graphs

- Computer Science, Mathematics
- DISC
- 2019

This work gives the first Byzantine-tolerant algorithm for a variant of lattice agreement and shows tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures. Expand

Optimal Resilience Asynchronous Approximate Agreement

- Computer Science
- OPODIS
- 2004

This paper presents a deterministic optimal resilience approximate agreement algorithm that can tolerate any t Byzantine faults while requiring only 3t+1 processes. Expand

On processor coordination using asynchronous hardware

- Computer Science
- PODC '87
- 1987

It is shown that the coordination problem cannot be solved by means of a deterministic protocol even if the system consists of only two processors, and the impossibility result holds for the most powerful type of shared atomic registers and does not assume symmetric protocols. Expand

Are wait-free algorithms fast?

- Mathematics, Computer Science
- JACM
- 1994

An O(log <italic>n</italic>) time wait-free approximate agreement algorithm is presented; the complexity of this algorithm is within a small constant of the lower bound. Expand

Tight bounds for k-set agreement

- Computer Science
- JACM
- 2000

The proof of this result is interesting because it is the first to apply topological techniques to the synchronous model and proves tight bounds on the time needed to solve k-set agreement. Expand

Easy impossibility proofs for distributed consensus problems

- Computer Science
- Distributed Computing
- 2005

Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in… Expand