pith. sign in

arxiv: 2606.24666 · v1 · pith:AYYNQVEZnew · submitted 2026-06-23 · 💻 cs.DC

Solvability of Approximate Agreement on Graphs and Simplicial Complexes

Joel Rybicki , Yaroslav Verbitsky This is my paper

Pith reviewed 2026-06-25 22:43 UTC · model grok-4.3

classification 💻 cs.DC
keywords approximate agreementclique complextopological characterizationasynchronous shared memoryresilient solvabilitydistributed computinggraph agreement tasks
0
0 comments X

The pith

Approximate agreement on a graph is t-resilient solvable exactly when its clique complex is (t-1)-connected.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a complete topological characterization of t-resilient solvability for approximate agreement tasks on graphs and simplicial complexes in asynchronous shared-memory systems. It proves that clique agreement on graph G holds if and only if the clique complex of G is (t-1)-connected. This settles open questions such as Ledent's conjecture on wait-free solvability and shows that clique and monophonic agreement coincide while separating from geodesic agreement. Readers would care because the result draws a sharp line between solvable and unsolvable instances of these relaxed consensus problems.

Core claim

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. This supplies the full characterization for approximate agreement on graphs and simplicial complexes and yields new resilience bounds for message-passing systems plus round lower bounds for synchronous systems.

What carries the argument

The homotopical (t-1)-connectivity of the clique complex of the input graph, which decides whether the required continuous map exists in the topological model of computation.

If this is right

  • Clique agreement and monophonic agreement are solvable on exactly the same class of graphs.
  • Monophonic agreement and geodesic agreement are separated on some graphs.
  • New resilience bounds hold for asynchronous approximate agreement in the message-passing model.
  • Round lower bounds follow for synchronous approximate agreement on graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Connectivity checks on clique complexes could classify solvability for new families of graphs without constructing protocols directly.
  • The same topological lens might yield characterizations for other graph-based tasks such as set agreement.
  • The separation between convexity notions suggests that different agreement variants may require distinct algorithmic techniques.

Load-bearing premise

The topological model using simplicial complexes and homotopical connectivity accurately captures the computational power and failure models of asynchronous shared-memory systems with read-write registers.

What would settle it

A graph whose clique complex is (t-1)-connected yet admits no t-resilient protocol for clique agreement in the asynchronous shared-memory model, or the converse case of a non-connected complex that still has a working protocol.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper provides a complete topological characterization of t-resilient solvability for approximate agreement tasks (including clique agreement) on graphs and simplicial complexes in asynchronous shared-memory read-write systems. The central result states that clique agreement is t-resilient solvable on graph G if and only if the clique complex of G is (t-1)-connected in the homotopical sense; this is used to prove Ledent's conjecture on wait-free solvability of clique agreement, establish equivalence of clique and monophonic agreement solvability, separate monophonic from geodesic agreement, and derive new resilience and round-complexity bounds in message-passing models.

Significance. If the characterization holds, the work resolves multiple open questions in distributed computing by supplying an if-and-only-if topological criterion that directly links task solvability to homotopical connectivity of the input complex. It supplies the first proof of Ledent's conjecture and cleanly separates agreement variants, strengthening the standard simplicial-complex model of asynchronous computation.

minor comments (3)
  1. The abstract and introduction would benefit from an explicit statement of the precise failure model (e.g., number of crashes, asynchrony assumptions) used for the t-resilient case, to make the modeling assumptions immediately visible to readers unfamiliar with the carrier-map framework.
  2. Notation for the clique complex and its connectivity is introduced without a dedicated preliminary section; adding a short subsection that recalls the definition of homotopical (t-1)-connectivity and the carrier map would improve readability.
  3. The message-passing corollaries are stated only at the end; moving a brief summary of the implied resilience bounds into the introduction would help readers assess the breadth of the results.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their thorough and positive evaluation of our manuscript. We are pleased that the work is recognized for providing a complete topological characterization, proving Ledent's conjecture, and separating agreement variants. The recommendation for minor revision is noted; as no specific major comments were raised, we interpret this as an invitation to incorporate any minor editorial or presentational suggestions during revision.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation establishes an if-and-only-if topological characterization of t-resilient solvability for clique agreement via (t-1)-connectivity of the clique complex. This rests on the standard simplicial-complex modeling of asynchronous read-write shared memory (carrier maps, protocol complexes) and homotopy as the obstruction to task solvability, both of which are external to the paper and not derived from its own fitted values or prior self-citations. The proof of Ledent's conjecture and the separation results between agreement variants are presented as consequences of these independent topological properties rather than reductions by construction. No self-definitional steps, fitted-input predictions, or load-bearing self-citation chains appear in the provided abstract or claim structure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result relies on established concepts from algebraic topology applied to distributed computing models; no free parameters or new entities are introduced based on the abstract.

axioms (1)
  • standard math Standard properties of simplicial complexes, convex hulls on graphs, and homotopical connectivity from algebraic topology.
    The solvability characterization is expressed directly in terms of these pre-existing mathematical structures.

pith-pipeline@v0.9.1-grok · 5810 in / 1302 out tokens · 32983 ms · 2026-06-25T22:43:36.789263+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages

  1. [1]

    Optimal resilience asynchronous approximate agreement

    1 Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approximate agreement. InProceedings of the Eighth International Conference on Principles of Distributed Systems (OPODIS 2004), pages 229–239, 2004.doi:10.1007/11516798_17. 2 Manuel Alcántara, Armando Castañeda, David Flores-Peñaloza, and Sergio Rajsbaum. The topology of look-...

    work page doi:10.1007/11516798_17 2004

  2. [2]

    5 Hagit Attiya, Amotz Bar-Noy, and Danny Dolev

    doi:10.4230/LIPIcs.OPODIS.2025.24. 5 Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems.Journal of the ACM (JACM), 42(1):124–142, 1995.doi:10.1145/200836.200869. 6 Hagit Attiya and Faith Ellen. The step complexity of multidimensional approximate agreement. In26th International Conference on Principles of Distr...

    work page doi:10.4230/lipics.opodis.2025.24 2025

  3. [3]

    13 Benny Chor, Amos Israeli, and Ming Li

    doi: 10.1186/s13173-017-0065-8. 13 Benny Chor, Amos Israeli, and Ming Li. On processor coordination using asynchronous hardware. InProceedings of the Sixth Annual ACM Symposium on Principles of distributed computing, pages 86–97, 1987.doi:10.1145/41840.41848. 14 BA Coan. A compiler that increases the fault tolerance of asynchronous protocols.IEEE Transact...

    work page doi:10.1186/s13173-017-0065-8 1987

  4. [4]

    16 Giuseppe Antonio Di Luna, Emmanuelle Anceaume, Silvia Bonomi, and Leonardo Querzoni

    doi:10.4230/LIPIcs.DISC.2024.15. 16 Giuseppe Antonio Di Luna, Emmanuelle Anceaume, Silvia Bonomi, and Leonardo Querzoni. Synchronous byzantine lattice agreement inO(logf )rounds. In2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pages 146–156. IEEE,

    work page doi:10.4230/lipics.disc.2024.15 2024

  5. [5]

    17 Danny Dolev, Nancy A

    doi: 10.1109/ICDCS47774.2020.00056. 17 Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults.Journal of the ACM, 33(3):499–516, May 1986.doi:10.1145/5925.5931. 18 Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous approximate agreement with quadratic communicatio...

    work page doi:10.1109/icdcs47774.2020.00056 2020

  6. [6]

    19 Jose M Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani

    doi: 10.4230/LIPIcs.OPODIS.2025.16. 19 Jose M Faleiro, Sriram Rajamani, Kaushik Rajan, Ganesan Ramalingam, and Kapil Vaswani. Generalized lattice agreement. InProceedings of the 2012 ACM Symposium on Principles of distributed computing, pages 125–134, 2012.doi:10.1145/2332432.2332458. 20 Martin Farber and Robert E Jamison. On local convexity in graphs.Dis...

    work page doi:10.4230/lipics.opodis.2025.16 2025

  7. [7]

    27 Eli Gafni and Elias Koutsoupias

    Association for Computing Machinery.doi:10.1145/277697.277724. 27 Eli Gafni and Elias Koutsoupias. Three-processor tasks are undecidable.SIAM Journal on Computing, 28(3):970–983, 1998.doi:10.1137/S0097539796305766. 28 Diana Ghinea and Chen-Da Liu-Zhang. Sok: Approximate agreement.Cryptology ePrint Archive,

    work page doi:10.1145/277697.277724 1998

  8. [8]

    Network-agnostic multidimensional approximate agreement with optimal resilience

    29 Diana Ghinea, Darya Melnyk, and Tijana Milentijević. Network-agnostic multidimensional approximate agreement with optimal resilience. InProceedings of the 2026 ACM Symposium on Principles of Distributed Computing,

    2026

  9. [9]

    Morgan Kaufmann, San Francisco, CA, 2014

    31 Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum.Distributed Computing Through Com- binatorial Topology. Morgan Kaufmann Publishers Inc., 2013.doi:10.1016/C2011-0-07032-1. 32 Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). InProceedings of the 29th Annual ACM Symposium on Theory of Computing (...

    work page doi:10.1016/c2011-0-07032-1 2013

  10. [10]

    Displaying trees across two phylogenetic networks

    doi:10.1016/j.tcs. 2009.01.033. 42 Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K Garg. Multidimensional agreement in byzantine systems.Distributed Computing, 28(6):423–441, 2015.doi:10.1007/ s00446-014-0240-5. 24 Solvability of Approximate Agreement on Graphs and Simplicial Complexes 43 Thomas Nowak and Joel Rybicki. Byzantine approximate a...

    work page doi:10.1016/j.tcs 2009

  11. [11]

    doi:10.4230/LIPIcs.DISC.2019

    work page doi:10.4230/lipics.disc.2019 2019

  12. [12]

    Vertex-to-vertex pursuit in a graph.Discrete Mathematics, 43(2-3):235–239, 1983.doi:10.1016/0012-365X(83)90160-7

    44 Richard Nowakowski and Peter Winkler. Vertex-to-vertex pursuit in a graph.Discrete Mathematics, 43(2-3):235–239, 1983.doi:10.1016/0012-365X(83)90160-7. 45 Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults.Journal of the ACM, 27(2):228–234, 1980.doi:10.1145/322186.322188. 46 Michael O. Rabin. Recursiv...

    work page doi:10.1016/0012-365x(83)90160-7 1983

  13. [13]

    48 Zhuolun Xiang and Nitin H Vaidya

    doi: 10.1109/SFCS.1995.492673. 48 Zhuolun Xiang and Nitin H Vaidya. Relaxed byzantine vector consensus. In20th International Conference on Principles of Distributed Systems (OPODIS 2016), Schloss Dagstuhl–Leibniz- Zentrum für Informatik, 2017.doi:10.4230/LIPIcs.OPODIS.2016.26. 49 Xiong Zheng and Vijay Garg. Byzantine Lattice Agreement in Asynchronous Syst...

    work page doi:10.1109/sfcs.1995.492673 1995