Search papers, labs, and topics across Lattice.
This paper provides a comprehensive topological characterization of the $t$-resilient solvability of approximate agreement tasks on graphs and simplicial complexes within asynchronous shared-memory systems. The authors resolve several open problems, including the first proof of Ledent's conjecture regarding wait-free clique agreement, establishing that clique agreement is $t$-resilient solvable if and only if its clique complex is $(t-1)$-connected. Additionally, the study reveals a separation between monophonic and geodesic agreement, while also deriving new resilience bounds for asynchronous approximate agreement in the message-passing context.
The solvability of clique agreement hinges on the homotopical connectivity of its clique complex, reshaping our understanding of resilience in distributed systems.
Approximate agreement tasks on graphs are discrete relaxations of consensus, where each process in a distributed system is given as input a vertex on a graph $G$, and processes have to output vertices that lie on a clique of $G$ contained in the convex hull of the input vertices. Although such tasks have been widely studied in a variety of models, graph classes and notions of convexity, it remains largely open for which classes of graphs these problems are solvable in asynchronous systems. In this work, we give a complete topological characterisation of the $t$-resilient solvability of approximate agreement on graphs and simplicial complexes in asynchronous shared-memory systems with read-write registers. As a result, we answer several open problems related to different variants of approximate agreement on graphs. For example, we give the first proof of Ledent's conjecture [PODC 2021] about the wait-free solvability of clique agreement. In fact, we show a more general result: clique agreement is $t$-resilient solvable on a graph $G$ if and only if its clique complex is $(t-1)$-connected in the homotopical sense. We also show that clique and monophonic agreement are solvable on the same class of graphs, but there exists a separation between monophonic and geodesic agreement, answering a question by Alistarh et al. [TCS 2023]. In the message-passing setting, our results imply new resilience bounds for asynchronous approximate agreement and round lower bounds for synchronous approximate agreement on graphs.
