Solving Approximate Agreement on continuous and discrete spaces

Augustin Albert; Sergio Rajsbaum

arxiv: 2606.23260 · v1 · pith:LQ74VWW7new · submitted 2026-06-22 · 💻 cs.DC

Solving Approximate Agreement on continuous and discrete spaces

Augustin Albert , Sergio Rajsbaum This is my paper

Pith reviewed 2026-06-26 07:08 UTC · model grok-4.3

classification 💻 cs.DC

keywords approximate agreementwait-free solvabilityCUB spacessimplicial complexesconnectivitycrash failuresasynchronous shared memorysimplex validity

0 comments

The pith

ε-agreement is solvable in every CUB space, and simplex agreement on a simplicial complex is solvable for n+1 processes exactly when the complex is (n-1)-connected.

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

The paper establishes that approximate agreement remains solvable in a wait-free manner for any number of crash-prone asynchronous processes whenever the input space belongs to the broad class of CUB metric spaces. In the discrete setting the authors give a precise topological threshold: simplex agreement is solvable if and only if the input complex satisfies (n-1)-connectivity. A reader cares because the results unify and extend earlier solvability boundaries for one-dimensional intervals, multidimensional grids, and graphs under the same validity and agreement requirements.

Core claim

In every CUB space ε-agreement is solvable. For any simplicial complex C, simplex agreement with n+1 processes is solvable if and only if C is (n-1)-connected. The same topological condition also yields a proof of Ledent's conjecture and recovers the known thresholds for the plane, punctured plane, and graphs.

What carries the argument

CUB spaces (continuous metric spaces with a unique convexity) and (n-1)-connectivity of simplicial complexes (discrete case).

If this is right

The problem is solvable for every n in the plane but becomes unsolvable when a single point is removed.
For graphs, 2-process agreement is solvable exactly when the graph is connected, while 3 or more processes require the graph to be acyclic.
The same connectivity threshold decides solvability for any input complex under simplex validity.
The continuous result covers both the classical one-dimensional ε-agreement and all multidimensional approximate-agreement tasks.

Where Pith is reading between the lines

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

The connectivity threshold may serve as a template for characterizing solvability under other validity conditions that still force outputs into input simplices.
One could test whether the same (n-1)-connectivity criterion continues to hold when the model is strengthened to include more failure types or weakened to allow message-passing instead of registers.
The CUB result suggests that any space whose convexity can be uniquely recovered from the metric will inherit the same solvability guarantee.

Load-bearing premise

Validity is defined by requiring outputs to lie inside the convex hull of the inputs or inside the input simplex.

What would settle it

Exhibit either a CUB space together with a wait-free protocol that fails to produce ε-close outputs satisfying validity, or an (n-1)-connected complex on which no wait-free protocol solves simplex agreement for n+1 processes.

Figures

Figures reproduced from arXiv: 2606.23260 by Augustin Albert, Sergio Rajsbaum.

**Figure 1.** Figure 1: Contractibility and collapsibility of the standard 2-simplex. Left: a homotopy contracting the triangle to its midpoint. Right: a sequence of elementary collapses reducing it to a single vertex. Definition 5. A topological space X is n-connected for n ∈ N if it is nonempty, path connected, and its first n homotopy groups πk(|C|), 1 ≤ k ≤ n, are trivial, i.e., any continuous map S k → |C| from the k-sphere… view at source ↗

**Figure 2.** Figure 2: Two geometric simplicial complexes A and B in R 3 , together with a larger complex obtained by gluing copies of A and B along their boundary simplices, shown in an exploded view. More interestingly, we can construct graphs for which Theorem 2 applies, but no existing combinatorial criterion does. Consider the simplicial complex C in [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: Two geodesics in a convex bicombing, with corresponding points marked at t = 2 3 . The bicombing is convex: the red edge decreases in length from t = 0 to t = 0.4, then increases from t = 0.4 to t = 1. 5.1 Approximate agreement on CUB spaces In this section, we propose approximate agreement on CUB spaces [36,17] as a generalization of existing approximate agreement problems on metric spaces [11,31]. Let us… view at source ↗

**Figure 4.** Figure 4: An infinite subdivision of the unit edge in R. The pullback metric from the proper cubical complex assigns length 1 to each subdivided edge, making the subdivided edge unbounded. ≃ [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

**Figure 5.** Figure 5: A geometric simplicial complex C that is PL-homeomorphic to a CAT(0) cubical complex D. The subdivision induced by the PL-homeomorphism is shown with dashed edges and hollow vertices. Two points are depicted, along with the shortest path between them in the piecewise flat equilateral metric of D and in the pullback metric of C. In particular, the simplices of κ are not all σ-convex. (xi)i∈[n] of K. For al… view at source ↗

read the original abstract

We consider $n$ asynchronous processes prone to crashes, communicating via shared read-write registers, and study the wait-free solvability of approximate agreement: given inputs, processes must output values that are close to each other, and satisfy a validity property. At the very least, if inputs are identical, all outputs must equal that input. The problem has been studied for various input spaces: continuous, discrete, one-dimensional or multidimensional. For metric spaces, validity requires outputs to lie in the convex hull of the inputs. For graphs, and more generally simplicial complexes, several conditions exist. We focus on simplex validity: if inputs span a simplex $\sigma$, then outputs are in $\sigma$. Agreement requires that outputs span a simplex. Solvability depends on the input space, validity condition, and number of processes. For example, the problem is solvable for all $n$ in the plane, but only for $n \leq 2$ when removing a point. For a graph, solvability for $n=2$ holds iff the graph is connected, but $n\geq 3$ requires acyclicity. In the continuous setting, we consider CUB spaces: a broad class of metric spaces admitting a unique convexity definition, subsuming classical $\epsilon$-agreement on $[0,1]$ and $m$-dimensional approximate agreement. Our results show that $\epsilon$-agreement is solvable in every CUB space. In the discrete case, we prove that simplex agreement on a simplicial complex $\mathcal{C}$ is solvable for $n+1$ processes iff $\mathcal{C}$ is $(n-1)$-connected. We discuss several consequences, including a proof of a conjecture by Ledent.

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.

Desk Editor's Note private letter to a colleague

This paper gives a general solvability result for approximate agreement in all CUB spaces and an iff connectivity characterization for simplex agreement that settles Ledent's conjecture.

read the letter

The main things to know are that ε-agreement turns out to be solvable in every CUB space and that simplex agreement on a complex is solvable for n+1 processes exactly when the complex is (n-1)-connected.

The new pieces are the uniform treatment of CUB spaces, which pulls together earlier case-by-case results on intervals and higher-dimensional metric spaces, and the clean if-and-only-if statement for discrete complexes. Both directions are asserted, and the connectivity threshold gives a precise cutoff that earlier graph-specific results only reached for small n. The topological framing lines up directly with the validity conditions, and the modeling choices (unique convexity for CUB, simplex validity for the discrete case) are stated up front so the scope is clear.

The work is solid on the claims that are made. The continuous result covers the standard examples without extra parameters, and the discrete characterization resolves an open conjecture as a direct consequence. No internal contradictions appear in the stated results, and the assumptions do not hide circularity.

The soft spots are limited. The CUB property is a genuine restriction, so the continuous claim does not extend to arbitrary metric spaces, but that boundary is explicit. The necessity direction in the discrete case will need the full proof to confirm it handles the asynchronous crash model and register communication without gaps, though nothing in the abstract suggests a problem. Minor exposition tweaks might help readers who are not already deep in the topological distributed-computing literature.

This is for people already working with simplicial models and wait-free solvability. A reader who knows the prior results on graphs and low dimensions will see the value in the generalizations. It has enough substance and resolves stated open questions to deserve a serious referee rather than a desk reject.

Referee Report

0 major / 1 minor

Summary. The paper studies wait-free solvability of approximate agreement (with validity) for n crash-prone asynchronous processes using read-write registers. In the continuous case it defines CUB spaces (metric spaces with unique convexity, subsuming [0,1] and m-dimensional approximate agreement) and claims that ε-agreement is solvable in every CUB space. In the discrete case it claims that simplex agreement on a simplicial complex C is solvable for n+1 processes if and only if C is (n-1)-connected, and derives consequences including a proof of Ledent's conjecture.

Significance. If the claimed characterizations hold, the work unifies and generalizes prior solvability results across continuous metric spaces and discrete complexes, supplies an iff topological condition for the discrete case, and resolves an open conjecture; the modeling assumptions (CUB with unique convexity; simplex validity) are explicitly stated and delimit the scope.

minor comments (1)

The abstract asserts existence of proofs for both directions of the discrete iff claim and for the continuous result, but the provided text does not include the derivations or section references to them; verification of the central claims therefore cannot be completed from the given material.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the manuscript and for recognizing the potential significance of the results in unifying continuous and discrete cases of approximate agreement, as well as resolving Ledent's conjecture. The recommendation is listed as 'uncertain,' but the report contains no specific major comments or questions to address. We remain available to provide clarifications or revisions should any concerns arise upon further review.

Circularity Check

0 steps flagged

No significant circularity; derivations are independent topological characterizations

full rationale

The paper establishes solvability of ε-agreement in all CUB spaces (continuous case) and an iff characterization of simplex agreement solvability precisely when the complex is (n-1)-connected (discrete case for n+1 processes). These are new mathematical results relying on topological connectivity arguments and validity conditions that are explicitly stated as modeling choices delimiting the problem instances, not as self-referential definitions. No steps reduce by construction to fitted inputs, self-citations that bear the central load, or ansatzes imported from prior author work; the proof of Ledent's conjecture is an external consequence rather than a circular dependency. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard distributed computing model and topological assumptions about the input spaces.

axioms (2)

domain assumption Asynchronous processes prone to crashes communicate via shared read-write registers in wait-free manner.
This is the standard model used for the solvability study.
domain assumption For metric spaces, validity requires outputs in convex hull; for complexes, simplex validity.
The paper focuses on these validity conditions.

pith-pipeline@v0.9.1-grok · 5837 in / 1437 out tokens · 37876 ms · 2026-06-26T07:08:18.338933+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

43 extracted references · 10 canonical work pages

[1]

Proceedings of the American Mathematical Society144(8), 3317–3329 (2016)

Adiprasito, K., Nevo, E., Samper, J.: Higher chordality: from graphs to complexes. Proceedings of the American Mathematical Society144(8), 3317–3329 (2016)

2016
[2]

Adiprasito, K.A., Funar, L.: Cat(0) metrics on contractible manifolds (2021), https: //arxiv.org/abs/1512.06403

arXiv 2021
[3]

alcántara et al

Alcántara, M., Castañeda, A., Flores-Peñaloza, D., Rajsbaum, S.: The topology of look-compute-move robot wait-free algorithms with hard termination: M. alcántara et al. Distributed Computing32(3), 235–255 (2019)

2019
[4]

Theoretical Computer Science948, 113733 (2023)

Alistarh, D., Ellen, F., Rybicki, J.: Wait-free approximate agreement on graphs. Theoretical Computer Science948, 113733 (2023)

2023
[5]

Björner, A., Wachs, M.: Shellable nonpure complexes and posets. i. Transactions of the American mathematical society348(4), 1299–1327 (1996)

1996
[6]

Advances in mathematics243, 127–167 (2013)

Brešar, B., Chalopin, J., Chepoi, V., Gologranc, T., Osajda, D.: Bucolic complexes. Advances in mathematics243, 127–167 (2013)

2013
[7]

Mathe- matica Scandinavica29(2), 197–205 (1971)

Bruggesser, H., Mani, P.: Shellable decompositions of cells and spheres. Mathe- matica Scandinavica29(2), 197–205 (1971)

1971
[8]

Journal of the Brazilian Computer Society24(1), 1 (2018)

Castañeda, A., Rajsbaum, S., Roy, M.: Convergence and covering on graphs for wait-free robots. Journal of the Brazilian Computer Society24(1), 1 (2018)

2018
[9]

Information and Computation105(1), 132–158 (1993)

Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation105(1), 132–158 (1993)

1993
[10]

Deutsch, F., Deutsch, F.: Best approximation in inner product spaces, vol. 7. Springer (2001)

2001
[11]

Journal of the ACM (JACM)33(3), 499–516 (1986)

Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approx- imate agreement in the presence of faults. Journal of the ACM (JACM)33(3), 499–516 (1986)

1986
[12]

Advances in neural information processing systems34, 25044–25057 (2021)

El-Mhamdi, E.M., Farhadkhani, S., Guerraoui, R., Guirguis, A., Hoang, L.N., Rouault, S.: Collaborative learning in the jungle (decentralized, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in neural information processing systems34, 25044–25057 (2021)

2021
[13]

Journal of the ACM (JACM)32(2), 374–382 (1985)

Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM)32(2), 374–382 (1985)

1985
[14]

Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Com- put.28(3), 970–983 (1999). https://doi.org/10.1137/S0097539796305766, https: //doi.org/10.1137/S0097539796305766

work page doi:10.1137/s0097539796305766 1999
[15]

Journal of the ACM (JACM)66(3), 1–18 (2019)

Goaoc, X., Paták, P., Patáková, Z., Tancer, M., Wagner, U.: Shellability is np- complete. Journal of the ACM (JACM)66(3), 1–18 (2019)

2019
[16]

essays in group theory

Gromov, M.: Hyperbolic groups, in “essays in group theory”. edited by sm gersten, msri publ. 8 (1987)

1987
[17]

Mathema- tische Annalen393(2), 1939–1987 (2025)

Haettel, T.: A link condition for simplicial complexes, and cub spaces. Mathema- tische Annalen393(2), 1939–1987 (2025)

1939
[18]

Cambridge university press, New York (2001)

Hatcher, A.: Algebraic topology. Cambridge university press, New York (2001)

2001
[19]

Distributed Computing13(2), 59–83 (2000)

Havlicek, J.: Computable obstructions to wait-free computability. Distributed Computing13(2), 59–83 (2000). https://doi.org/10.1007/s004460050068

work page doi:10.1007/s004460050068 2000
[20]

Newnes (2013)

Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed computing through combina- torial topology. Newnes (2013)

2013
[21]

In: Pro- ceedings of the twenty-ninth annual ACM symposium on Theory of computing

Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks. In: Pro- ceedings of the twenty-ninth annual ACM symposium on Theory of computing. pp. 589–598 (1997) 18 Augustin Albert, Sergio Rajsbaum

1997
[22]

Herlihy,M.,Rajsbaum,S.:Aclassificationofwait-freeloopagreementtasks.Theor. Comput. Sci.291(1), 55–77 (2003). https://doi.org/10.1016/S0304-3975(01) 00396-6

work page doi:10.1016/s0304-3975(01 2003
[23]

Theoretical Computer Science683, 1–21 (2017)

Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: From wait-free to arbitrary con- current solo executions in colorless distributed computing. Theoretical Computer Science683, 1–21 (2017). https://doi.org/10.1016/j.tcs.2017.04.007

work page doi:10.1016/j.tcs.2017.04.007 2017
[24]

In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing

Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. pp. 111–120 (1993)

1993
[25]

Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM46(6), 858–923 (Nov 1999). https://doi.org/10.1145/331524.331529

work page doi:10.1145/331524.331529 1999
[26]

Pacific Journal of Mathematics38(2), 471–485 (1971)

Kay, D., Womble, E.W.: Axiomatic convexity theory and relationships between the carathéodory, helly, and radon numbers. Pacific Journal of Mathematics38(2), 471–485 (1971)

1971
[27]

In: PODC ’21: ACM Symposium on Principles of Distributed Computing

Ledent, J.: Brief announcement: Variants of approximate agreement on graphs and simplicial complexes. In: PODC ’21: ACM Symposium on Principles of Distributed Computing. pp. 427–430. ACM (2021). https://doi.org/10.1145/3465084.3467946

work page doi:10.1145/3465084.3467946 2021
[28]

In: 26th International Conference on Principles of Distributed Systems, OPODIS

Liu, S.: The impossibility of approximate agreement on a larger class of graphs. In: 26th International Conference on Principles of Distributed Systems, OPODIS
[29]

22:1–22:20

pp. 22:1–22:20. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPICS.OPODIS.2022.22

work page doi:10.4230/lipics.opodis.2022.22 2022
[30]

Foundations of Data Science (2026)

Liu, X., Theriault, S., Wu, J., Yue, Y.: Homotopy theory and distributed comput- ing. Foundations of Data Science (2026). https://doi.org/10.3934/fods.2026011

work page doi:10.3934/fods.2026011 2026
[31]

Liu,X.,Xu,Z., Pan, J.:Classifyingrendezvoustasksofarbitrarydimension.Theor. Comput. Sci.410(21-23), 2162–2173 (2009). https://doi.org/10.1016/J.TCS.2009. 01.033

work page doi:10.1016/j.tcs.2009 2009
[32]

Distributed Computing28(6), 423–441 (2015)

Mendes, H., Herlihy, M., Vaidya, N., Garg, V.K.: Multidimensional agreement in byzantine systems. Distributed Computing28(6), 423–441 (2015)

2015
[33]

Chap- man and Hall/CRC (2025)

Munkres, J.R., Krantz, S.G., Parks, H.R.: Elements of algebraic topology. Chap- man and Hall/CRC (2025)

2025
[34]

In: 33rd International Symposium on Distributed Computing, DISC 2019

Nowak, T., Rybicki, J.: Byzantine approximate agreement on graphs. In: 33rd International Symposium on Distributed Computing, DISC 2019. pp. 29:1–29:17. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/ 10.4230/LIPICS.DISC.2019.29

work page doi:10.4230/lipics.disc.2019.29 2019
[35]

arXiv preprint arXiv:1305.4661 (2013)

Osajda, D.: A combinatorial non-positive curvature i: weak systolicity. arXiv preprint arXiv:1305.4661 (2013)

Pith/arXiv arXiv 2013
[36]

Princeton Uni- versity (1956)

Rabin, M.O.: Recursive unsolvability of group theoretic problems. Princeton Uni- versity (1956)

1956
[37]

arXiv preprint arXiv:1607.07747 (2016)

Roller, M.: Poc sets, median algebras and group actions. arXiv preprint arXiv:1607.07747 (2016)

Pith/arXiv arXiv 2016
[38]

In: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Stolz, D., Wattenhofer, R.: Byzantine Agreement with Median Validity. In: 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp. 22:1–22:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016). https://doi.org/10. 4230/LIPIcs.OPODIS.2015.22

2015
[39]

Annali di Matematica Pura ed Applicata29(1), 25–30 (1949)

Stone, M.H.: Postulates for the barycentric calculus. Annali di Matematica Pura ed Applicata29(1), 25–30 (1949)

1949
[40]

In: Proceedings of the 2016 ACM symposium on principles of distributed computing

Su, L., Vaidya, N.H.: Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In: Proceedings of the 2016 ACM symposium on principles of distributed computing. pp. 425–434 (2016) Solving Approximate Agreement on continuous and discrete spaces 19 A Proofs of Section 5.1: inequality results in CUB spaces In this section, we prove ...

2016
[41]

Symmetrically,d(x, ∆∩τ)≤C mδ < d min/2

Now,d(∆, κ)≤d(x, κ)< d min so∆∩κ̸=∅andd(x, ∆∩κ)≤C mδ < dmin/2. Symmetrically,d(x, ∆∩τ)≤C mδ < d min/2. Therefore,∆∩κand∆∩τ intersects. In particular,κ∩τ̸=∅. Moreover, we have: d(x, κ∩τ)≤d(x,(∆∩κ)∩(∆∩τ))≤C 2 mδ. Therefore, havingC=C 2 m suffices. Proof (of Proposition 2).Let us show by induction that after thekth round, the processes’ points lie either in ...
[42]

every(k−1)-clique inAis contained in exactly twok-cliques inA
[43]

Theorem 8.If a graphGsatisfies thek-clique containment, then its clique complexCl(G)is not(k−1)-connected

there is ak-clique inAthat is not contained in any(k+ 1)-clique inG. Theorem 8.If a graphGsatisfies thek-clique containment, then its clique complexCl(G)is not(k−1)-connected. Proof.In the following, we consider the homology ofCl(G)with coefficients in Z/2Z. LetSbe the sum of all(k−1)-simplices that correspond tok-cliques of the subgraphA. By the first co...

[1] [1]

Proceedings of the American Mathematical Society144(8), 3317–3329 (2016)

Adiprasito, K., Nevo, E., Samper, J.: Higher chordality: from graphs to complexes. Proceedings of the American Mathematical Society144(8), 3317–3329 (2016)

2016

[2] [2]

Adiprasito, K.A., Funar, L.: Cat(0) metrics on contractible manifolds (2021), https: //arxiv.org/abs/1512.06403

arXiv 2021

[3] [3]

alcántara et al

Alcántara, M., Castañeda, A., Flores-Peñaloza, D., Rajsbaum, S.: The topology of look-compute-move robot wait-free algorithms with hard termination: M. alcántara et al. Distributed Computing32(3), 235–255 (2019)

2019

[4] [4]

Theoretical Computer Science948, 113733 (2023)

Alistarh, D., Ellen, F., Rybicki, J.: Wait-free approximate agreement on graphs. Theoretical Computer Science948, 113733 (2023)

2023

[5] [5]

Björner, A., Wachs, M.: Shellable nonpure complexes and posets. i. Transactions of the American mathematical society348(4), 1299–1327 (1996)

1996

[6] [6]

Advances in mathematics243, 127–167 (2013)

Brešar, B., Chalopin, J., Chepoi, V., Gologranc, T., Osajda, D.: Bucolic complexes. Advances in mathematics243, 127–167 (2013)

2013

[7] [7]

Mathe- matica Scandinavica29(2), 197–205 (1971)

Bruggesser, H., Mani, P.: Shellable decompositions of cells and spheres. Mathe- matica Scandinavica29(2), 197–205 (1971)

1971

[8] [8]

Journal of the Brazilian Computer Society24(1), 1 (2018)

Castañeda, A., Rajsbaum, S., Roy, M.: Convergence and covering on graphs for wait-free robots. Journal of the Brazilian Computer Society24(1), 1 (2018)

2018

[9] [9]

Information and Computation105(1), 132–158 (1993)

Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation105(1), 132–158 (1993)

1993

[10] [10]

Deutsch, F., Deutsch, F.: Best approximation in inner product spaces, vol. 7. Springer (2001)

2001

[11] [11]

Journal of the ACM (JACM)33(3), 499–516 (1986)

Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approx- imate agreement in the presence of faults. Journal of the ACM (JACM)33(3), 499–516 (1986)

1986

[12] [12]

Advances in neural information processing systems34, 25044–25057 (2021)

El-Mhamdi, E.M., Farhadkhani, S., Guerraoui, R., Guirguis, A., Hoang, L.N., Rouault, S.: Collaborative learning in the jungle (decentralized, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in neural information processing systems34, 25044–25057 (2021)

2021

[13] [13]

Journal of the ACM (JACM)32(2), 374–382 (1985)

Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM)32(2), 374–382 (1985)

1985

[14] [14]

Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Com- put.28(3), 970–983 (1999). https://doi.org/10.1137/S0097539796305766, https: //doi.org/10.1137/S0097539796305766

work page doi:10.1137/s0097539796305766 1999

[15] [15]

Journal of the ACM (JACM)66(3), 1–18 (2019)

Goaoc, X., Paták, P., Patáková, Z., Tancer, M., Wagner, U.: Shellability is np- complete. Journal of the ACM (JACM)66(3), 1–18 (2019)

2019

[16] [16]

essays in group theory

Gromov, M.: Hyperbolic groups, in “essays in group theory”. edited by sm gersten, msri publ. 8 (1987)

1987

[17] [17]

Mathema- tische Annalen393(2), 1939–1987 (2025)

Haettel, T.: A link condition for simplicial complexes, and cub spaces. Mathema- tische Annalen393(2), 1939–1987 (2025)

1939

[18] [18]

Cambridge university press, New York (2001)

Hatcher, A.: Algebraic topology. Cambridge university press, New York (2001)

2001

[19] [19]

Distributed Computing13(2), 59–83 (2000)

Havlicek, J.: Computable obstructions to wait-free computability. Distributed Computing13(2), 59–83 (2000). https://doi.org/10.1007/s004460050068

work page doi:10.1007/s004460050068 2000

[20] [20]

Newnes (2013)

Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed computing through combina- torial topology. Newnes (2013)

2013

[21] [21]

In: Pro- ceedings of the twenty-ninth annual ACM symposium on Theory of computing

Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks. In: Pro- ceedings of the twenty-ninth annual ACM symposium on Theory of computing. pp. 589–598 (1997) 18 Augustin Albert, Sergio Rajsbaum

1997

[22] [22]

Herlihy,M.,Rajsbaum,S.:Aclassificationofwait-freeloopagreementtasks.Theor. Comput. Sci.291(1), 55–77 (2003). https://doi.org/10.1016/S0304-3975(01) 00396-6

work page doi:10.1016/s0304-3975(01 2003

[23] [23]

Theoretical Computer Science683, 1–21 (2017)

Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: From wait-free to arbitrary con- current solo executions in colorless distributed computing. Theoretical Computer Science683, 1–21 (2017). https://doi.org/10.1016/j.tcs.2017.04.007

work page doi:10.1016/j.tcs.2017.04.007 2017

[24] [24]

In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing

Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. pp. 111–120 (1993)

1993

[25] [25]

Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM46(6), 858–923 (Nov 1999). https://doi.org/10.1145/331524.331529

work page doi:10.1145/331524.331529 1999

[26] [26]

Pacific Journal of Mathematics38(2), 471–485 (1971)

Kay, D., Womble, E.W.: Axiomatic convexity theory and relationships between the carathéodory, helly, and radon numbers. Pacific Journal of Mathematics38(2), 471–485 (1971)

1971

[27] [27]

In: PODC ’21: ACM Symposium on Principles of Distributed Computing

Ledent, J.: Brief announcement: Variants of approximate agreement on graphs and simplicial complexes. In: PODC ’21: ACM Symposium on Principles of Distributed Computing. pp. 427–430. ACM (2021). https://doi.org/10.1145/3465084.3467946

work page doi:10.1145/3465084.3467946 2021

[28] [28]

In: 26th International Conference on Principles of Distributed Systems, OPODIS

Liu, S.: The impossibility of approximate agreement on a larger class of graphs. In: 26th International Conference on Principles of Distributed Systems, OPODIS

[29] [29]

22:1–22:20

pp. 22:1–22:20. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPICS.OPODIS.2022.22

work page doi:10.4230/lipics.opodis.2022.22 2022

[30] [30]

Foundations of Data Science (2026)

Liu, X., Theriault, S., Wu, J., Yue, Y.: Homotopy theory and distributed comput- ing. Foundations of Data Science (2026). https://doi.org/10.3934/fods.2026011

work page doi:10.3934/fods.2026011 2026

[31] [31]

Liu,X.,Xu,Z., Pan, J.:Classifyingrendezvoustasksofarbitrarydimension.Theor. Comput. Sci.410(21-23), 2162–2173 (2009). https://doi.org/10.1016/J.TCS.2009. 01.033

work page doi:10.1016/j.tcs.2009 2009

[32] [32]

Distributed Computing28(6), 423–441 (2015)

Mendes, H., Herlihy, M., Vaidya, N., Garg, V.K.: Multidimensional agreement in byzantine systems. Distributed Computing28(6), 423–441 (2015)

2015

[33] [33]

Chap- man and Hall/CRC (2025)

Munkres, J.R., Krantz, S.G., Parks, H.R.: Elements of algebraic topology. Chap- man and Hall/CRC (2025)

2025

[34] [34]

In: 33rd International Symposium on Distributed Computing, DISC 2019

Nowak, T., Rybicki, J.: Byzantine approximate agreement on graphs. In: 33rd International Symposium on Distributed Computing, DISC 2019. pp. 29:1–29:17. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/ 10.4230/LIPICS.DISC.2019.29

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

[35] [35]

arXiv preprint arXiv:1305.4661 (2013)

Osajda, D.: A combinatorial non-positive curvature i: weak systolicity. arXiv preprint arXiv:1305.4661 (2013)

Pith/arXiv arXiv 2013

[36] [36]

Princeton Uni- versity (1956)

Rabin, M.O.: Recursive unsolvability of group theoretic problems. Princeton Uni- versity (1956)

1956

[37] [37]

arXiv preprint arXiv:1607.07747 (2016)

Roller, M.: Poc sets, median algebras and group actions. arXiv preprint arXiv:1607.07747 (2016)

Pith/arXiv arXiv 2016

[38] [38]

In: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Stolz, D., Wattenhofer, R.: Byzantine Agreement with Median Validity. In: 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp. 22:1–22:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016). https://doi.org/10. 4230/LIPIcs.OPODIS.2015.22

2015

[39] [39]

Annali di Matematica Pura ed Applicata29(1), 25–30 (1949)

Stone, M.H.: Postulates for the barycentric calculus. Annali di Matematica Pura ed Applicata29(1), 25–30 (1949)

1949

[40] [40]

In: Proceedings of the 2016 ACM symposium on principles of distributed computing

Su, L., Vaidya, N.H.: Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In: Proceedings of the 2016 ACM symposium on principles of distributed computing. pp. 425–434 (2016) Solving Approximate Agreement on continuous and discrete spaces 19 A Proofs of Section 5.1: inequality results in CUB spaces In this section, we prove ...

2016

[41] [41]

Symmetrically,d(x, ∆∩τ)≤C mδ < d min/2

Now,d(∆, κ)≤d(x, κ)< d min so∆∩κ̸=∅andd(x, ∆∩κ)≤C mδ < dmin/2. Symmetrically,d(x, ∆∩τ)≤C mδ < d min/2. Therefore,∆∩κand∆∩τ intersects. In particular,κ∩τ̸=∅. Moreover, we have: d(x, κ∩τ)≤d(x,(∆∩κ)∩(∆∩τ))≤C 2 mδ. Therefore, havingC=C 2 m suffices. Proof (of Proposition 2).Let us show by induction that after thekth round, the processes’ points lie either in ...

[42] [42]

every(k−1)-clique inAis contained in exactly twok-cliques inA

[43] [43]

Theorem 8.If a graphGsatisfies thek-clique containment, then its clique complexCl(G)is not(k−1)-connected

there is ak-clique inAthat is not contained in any(k+ 1)-clique inG. Theorem 8.If a graphGsatisfies thek-clique containment, then its clique complexCl(G)is not(k−1)-connected. Proof.In the following, we consider the homology ofCl(G)with coefficients in Z/2Z. LetSbe the sum of all(k−1)-simplices that correspond tok-cliques of the subgraphA. By the first co...