REVIEW 2 major objections 3 minor 85 references
Byzantine Approximate Agreement on Graphs
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Approximate agreement on any chordal graph is solvable in an asynchronous Byzantine system in $O(\log |V|)$ rounds whenever $n>(\omega(G)+1)f$, with the outputs forming a clique inside the monophonic convex hull of the correct inputs.
desk verdict Solid algorithms for chordal graphs and cycle-free semilattices, but the general asynchronous impossibility theorem rests on a false lemma and needs repair. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the abstract convexity space, a collection of convex subsets closed under intersection, with its Helly number $\omega$ (the size of the largest free set, equal to the clique number for chordal-graph convexity) and Carathéodory number $c$ (the size of the largest irredundant set, at most two for graph convexities). The core mechanism is an iterative round in which each processor forms the convex hull of every set of $n-f$ values it received, intersects all those hulls, and maps the intersection to an extreme-point output; the Helly property keeps the intersection nonempty and inside the hull of the correct inputs. For chordal graphs, the round is run on an expanded clique tree, whose bags carry the tree algorithm's shrinking-diameter convergence, forcing the graph outputs onto a single clique. The lower bounds are built from blocking instances given by irredundant or free sets of the convexity space.
What would settle it
In Section 7.2, Lemma 15 claims that for any $a$ in an irredundant set $A$ and any $y\in\langle A\rangle\setminus A$, some $b\in A\setminus\{a\}$ has $y\notin\langle A\setminus\{b\}\rangle$. A direct test is to exhibit a five-element convexity space where that implication fails; if such a space exists, the Carathéodory-number lower bound in Theorem 11's first bullet would need a different blocking-instance argument, while the chordal-graph and semilattice results remain supported by the simpler size-two and free-chain instances.
Extended reading notes
Core claim
The central claim is that agreement tasks over discrete value sets become solvable when the value set carries a convexity with small Helly and Carathéodory numbers, even in asynchronous systems with Byzantine faults. On a chordal graph $G$, the monophonic (chordless-path) convexity has Helly number $\omega(G)$ and Carathéodory number at most two, and the paper proves that an iterative intersection-of-convex-hulls scheme converges in $O(\log |V|)$ asynchronous rounds under $n>(\omega(G)+1)f$, with all non-faulty outputs residing in a single clique contained in the monophonic hull of the non-faulty inputs. Since geodesic and monophonic convexities coincide on Ptolemaic graphs, geodesic approximate agreement is solvable there as well. The same abstract scheme produces the first Byzantine-tolerant lattice agreement on cycle-free semilattices, and in synchronous systems it yields exact convex consensus on any convexity space with finite Helly number $\omega$ in $\Theta(f)$ rounds if and only if $n>\max\{3f,\omega f\}$.
Load-bearing premise
The broadest impossibility result leans on the premise that from any minimal generating set of points in a convexity space you can always remove a different point and keep a chosen outside point out of the smaller hull; the graph and semilattice results do not need this premise in full generality.
Editorial extensions
If this is right
- Every chordal graph, including trees and interval graphs, admits a deterministic asynchronous Byzantine algorithm for monophonic approximate agreement with resilience $n>(\omega(G)+1)f$ and $O(\log |V|)$ rounds.
- On Ptolemaic graphs, geodesic approximate agreement, where outputs must lie on shortest paths between correct inputs, is solvable with the same resilience and the same round bound.
- Cycle-free semilattices admit Byzantine-tolerant lattice agreement, giving the first algorithm for any semilattice-agreement variant under Byzantine faults.
- In synchronous systems, exact convex consensus on any convexity space with Helly number $\omega$ can be solved in $\Theta(f)$ rounds if and only if $n>\max\{3f,\omega f\}$, and the upper bound does not require the space to be a convex geometry.
- No asynchronous algorithm can solve abstract approximate agreement when $n\le(c+1)f$, where $c$ is the Carathéodory number, and for convex geometries no algorithm satisfying validity can output fewer than $\omega-1$ distinct values when $n\le(\omega+1)f$.
Reading between the lines
- A testable extension is to apply the clique-tree lifting to non-chordal graph classes with bounded treewidth; the four-cycle shows that monophonic convexity need not be a convex geometry there, so such a lifting would require a different output rule or a different convexity.
- If the general blocking-instance lower bound can be repaired or re-proved, the asynchronous boundary would hinge on the Carathéodory number alone; the graph and semilattice results suggest the true solvability condition may involve the pair $(c,\omega)$ jointly.
- Because the synchronous reduction from convex consensus to multivalued Byzantine agreement is black-box, any future improvement in multivalued agreement round complexity would immediately improve convex consensus without redesigning the reduction.
- The discrete outputs and $O(\log |V|)$ bit complexity suggest practical use in protocols that operate on small finite value spaces, such as fault-tolerant clock or phase synchronisation, where real-valued approximate agreement would be needlessly heavy.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Byzantine fault-tolerant agreement when the value domain is a finite combinatorial structure rather than Euclidean space. It formulates an abstract approximate agreement problem on convexity spaces, whose agreement condition requires the output set to be free and whose validity condition requires outputs to lie in the convex hull of the correct inputs. The main positive results are an asynchronous monophonic approximate agreement algorithm for chordal graphs with O(log|V|) rounds when n>(ω(G)+1)f (Theorem 3), an asynchronous Byzantine lattice agreement algorithm for cycle-free semilattices (Theorem 4), and a synchronous convex consensus algorithm that is optimal in resilience and round complexity (Theorems 5-10). The paper also claims general asynchronous lower bounds parameterised by the Carathéodory and Helly numbers (Theorem 11). The algorithms are iterative generalizations of the Mendes-Herlihy and Vaidya-Garg frameworks, and the analysis is built on abstract convexity invariants such as Helly, Carathéodory, and free sets.
Significance. If the upper-bound results are correct, the paper makes a valuable contribution: it extends Byzantine approximate agreement from Euclidean spaces to discrete convexity spaces, gives the first Byzantine-tolerant lattice agreement algorithm for cycle-free semilattices, and avoids real-valued message passing by using O(log|V|)-bit values. The synchronous lower and upper bounds for convex consensus also appear coherent and generalize known Euclidean results. However, the advertised general asynchronous lower bound is currently not established because a load-bearing lemma is false as stated. The positive algorithmic results and the synchronous results are largely independent of that lemma, so the core contribution is still substantial, but the lower-bound section must be corrected or narrowed.
major comments (2)
- [7.2, Lemma 15] Lemma 15 is false as stated, and its proof is invalid. From y∈B one can only conclude y∉∂A, not y∉⟨A⟩∖A, because ∂A is a subset of ⟨A⟩∖A. A concrete counterexample is V={0,1,2,3,4} with the intersection-closed convexity space C={∅,V,{0,1},{2},{4},{0,1,2},{0,1,4},{2,4}}. For A={0,2,4}, one has ⟨A⟩=V, ⟨A∖{0}⟩={2,4}, ⟨A∖{2}⟩={0,1,4}, and ⟨A∖{4}⟩={0,1,2}; hence ∂A={3} and A is irredundant. Yet for a=0 and y=1∈⟨A⟩∖A, both candidates b∈A∖{0} satisfy y∈⟨A∖{b}⟩. Therefore Lemma 16 cannot define the required blocking map for this A, and the first bullet of Theorem 11, together with Corollary 3, is unsupported for arbitrary convexity spaces. The chordal-graph and semilattice upper bounds and the synchronous lower bounds do not depend on this lemma, but the general Carathéodory-number lower bound needs either a corrected proof or a restricted statement.
- [4.1, Lemmas 6 and 7] The convergence analysis for the tree algorithm contains assertions that are false as written, and these lemmas are load-bearing for Theorems 2 and 3. In Lemma 6, the proof asserts the existence of a vertex v∈center⟨X⟩∩⋂_{i}center H_i that is adjacent to every other vertex of ⟨X⟩; this fails when, for example, one H_i is a singleton leaf of a star and another H_i is the whole star. In Lemma 7, the proof asserts that for each k one can choose u_k∈T_k with d(u_k,y_k)=r(H_k); on a path, take H_i=[0..6], H_j=[3..8], a perfect elimination ordering for which y_j=6 is the maximum center of H_j, and B={4,5}; then T_j={6,7,8} contains no vertex at distance r(H_j)=3 from y_j. The displayed inequality D(H_i∪H_j)≥R(H_i)+R(H_j)+d(y_i,y_j) is therefore not established. The lemmas may be true, but the present arguments need to be repaired before the O(log|V|) chordal-graph claim can be considered proven.
minor comments (3)
- [4.2, Theorem 3] Lemma 11 is stated for interior nodes of H_i^T, but the final output bags can be leaves of T. The leaf case should be handled explicitly; one way is to observe that a leaf b∈H_i^T forces the existence of a set J⊆P_i of size |P_i|-f consisting only of processors whose current values lie in χ(b), so H_i⊆χ(b), and H_i is nonempty by Lemma 1.
- [4.1, Theorem 2] In the induction proof of Theorem 2, the step from D(X(t+1))≤D(X(0))/2^{t+1}+3/2 to the claimed bound D(X(0))/2^{t+1}+1 is not justified by integrality alone when the fraction D(X(0))/2^{t+1} has a large fractional part. The O(log|V|) round bound is unaffected, but the round count should be checked.
- [2.1] The notion of a free set is used informally in the introduction before it is defined in Section 2.1; a forward reference or a one-sentence definition at first use would improve readability.
Circularity Check
No significant circularity: the algorithms and bounds are derived from explicit hypotheses and independent prior art, with no fitted input, no target result assumed, and no load-bearing self-citation chain.
full rationale
The paper's central claims are new algorithmic constructions and impossibility bounds built on explicit assumptions: for chordal graphs it assumes n>(ω(G)+1)f and proves correctness via the Helly property, convex elimination orders, and an expanded clique tree; for cycle-free semilattices it assumes n>(ω+1)f and uses the algebraic convexity framework; for synchronous convex consensus it gives a reduction to multivalued Byzantine agreement cited from Srikanth–Toueg. No parameter is fitted to data, and no theorem is used as its own hypothesis. The only self-citations, the Lenzen–Rybicki clock-synchronization references, are contextual and not load-bearing. The known weakness in Lemma 15 is a correctness defect in the general asynchronous impossibility theorem, not a circularity: the proof's inference from y∉∂A to y∉⟨A⟩∖A is invalid, and the lemma is false for a five-element convexity space, but this does not make the derivation equivalent to its inputs, and the graph and semilattice corollaries do not depend on it. The conclusion's open problems explicitly acknowledge limitations rather than importing assumptions. No circular step can be quoted, so the honest finding is a score of 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Asynchronous round model with witness technique guarantees each correct processor receives at least n-f nonempty values, any two correct processors share at least n-f values, and faulty messages are consistent via reliable broadcast (Section 2.2).
- standard math Standard results in convexity theory: convex geometries satisfy the Minkowski-Krein-Milman property and the one-point extension property (Theorem 1); Helly number of chordless path convexity on chordal graphs equals clique number; Carathéodory number is at most 2; semilattice algebraic convexity…
- standard math Every chordal graph has an expanded clique tree with O(|V|) nodes (Lemma 9).
- domain assumption For a cycle-free semilattice, the perfect elimination order of the chordal comparability graph is a convex elimination order for the algebraic convexity (Lemma 12).
Cite this review
Pith. "Pith review of Byzantine Approximate Agreement on Graphs." pith.science (2026). https://pith.science/paper/JLK7BKK2
@misc{pith2026190802743,
author = {Pith},
title = {Pith review of: Byzantine Approximate Agreement on Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/JLK7BKK2}},
note = {Machine review of arXiv:1908.02743}
}
abstract
Consider a distributed system with $n$ processors out of which $f$ can be Byzantine faulty. In the approximate agreement task, each processor $i$ receives an input value $x_i$ and has to decide on an output value $y_i$ such that - the output values are in the convex hull of the non-faulty processors' input values, - the output values are within distance $d$ of each other. Classically, the values are assumed to be from an $m$-dimensional Euclidean space, where $m \ge 1$. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph $G$ and the goal is to output vertices that are within distance $d$ of each other in $G$, but still remain in the graph-induced convex hull of the input values. For $d=0$, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any $d \ge 1$, we show that the task is solvable in asynchronous systems when $G$ is chordal and $n > (\omega+1)f$, where $\omega$ is the clique number of~$G$. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
Figures
Reference graph
Works this paper leans on
-
[1]
the output values are in the convex hull of the non-faulty processors’ input values,
-
[2]
Byzantine Approximate Agreement on Graphs
the output values are within distanced of each other. Classically, the values are assumed to be from anm-dimensional Euclidean space, wherem≥ 1. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graphG and the goal is to output vertices tha...
work page Pith review arXiv 1908
-
[3]
A,B∈C implies A∩B∈C . As the name suggests, the sets inC are calledconvex and every convexity space has the natural closure operator, which maps any setA∈V to a minimal convex supersetA⊆⟨A⟩∈C called the convex hull ofA. Convex geometries[20] are an important class of convexity spaces, which satisfy the Minkowski-Krein-Milman property: the closure⟨A⟩ of an...
-
[4]
We give algorithms for approximate agreement on trees and chordal graphs
Byzantine approximate agreement on chordal graphs. We give algorithms for approximate agreement on trees and chordal graphs. The algorithms toleratef <n/(ω + 1) Byzantine faults and terminate inO(logN) asynchronous rounds, whereω is the clique number and N is the number of vertices in the value graphG. In trees, we achieve optimal resilience
-
[5]
To our knowledge, this is the first algorithm that solves any variant of semilattice agreement under Byzantine faults
Byzantine lattice agreement on cycle-free semilattices.As another example, we give an asynchronous lattice agreement algorithm on cycle-free lattices that tolerates up to f < n/(ω + 1) Byzantine faults, whereω is the height of the semilattice. To our knowledge, this is the first algorithm that solves any variant of semilattice agreement under Byzantine faults
-
[6]
General impossibility results for asynchronous systems. We give impossibility results for approximate agreement on arbitrary convex geometries parameterised by two combinatorial convexity invariants: the Carathéodory numberc and the Helly numberω. As corollaries, we obtain resilience lower bounds for approximate agreement problems in asynchronous systems
-
[7]
Optimal synchronous algorithms for convex consensus. We consider the exact variant of the abstract approximate agreement problem, where the agreement constraint is replaced by|Y| = 1. While the problem cannot be solved in asynchronous systems, we show that it can be solved on any convex geometryC in Θ(f) synchronous rounds if and only ifn>ωf holds, whereω...
-
[8]
C is a convex geometry
Show all 85 references
-
[9]
For everyK∈C , K =⟨exK⟩ (Minkowski-Krein-Milman property)
-
[10]
For everyK∈C\{ V}, there exists an elementu∈V\K such thatK∪{u}∈C . 6 2.1.1 Carathéodory and Helly numbers The Carathéodory numberof a convexity spaceC on V is the smallest integerc such that for any U⊆V and anyu∈⟨U⟩, there is a setS⊆U such that|S|≤ c and u∈⟨S⟩. The Carathéodor...
-
[11]
sends a value to each processorj∈P,
-
[12]
receives a valueMij(t) from each processorj∈P,
-
[13]
The received messageMij(t) may be empty, denoted by⊥, to indicate that no message arrived from processorj (e.g., due to a crash or a delay)
updates local state and proceeds to roundt + 1. The received messageMij(t) may be empty, denoted by⊥, to indicate that no message arrived from processorj (e.g., due to a crash or a delay). We use the set Pi(t) ={j∈P :Mij(t)⁄=⊥} to denote the processors from whichi received a n...
-
[14]
easy to peel
if Mik(t) =x⁄=⊥ for k∈F, thenMjk(t)∈{x,⊥}. That is, (1) every correct processor receives at leastn−f nonempty values (out of whichf may be from faulty processors), (2) any two correct processors receive at leastn−f common values 7 (possibly f of which may be from faulty proces...
-
[15]
Broadcast xi(t) and bi(t) to all other processors
-
[16]
Simulate one step ofA on theb(·) values and setbi(t + 1) = A (b0,i(t),...,b n−1,i(t))
-
[17]
Compute the safe areaHG i from the received valuesxij(t)
-
[18]
Since thebi(·) values are updated using the algorithmA, these values converge onto a single edge{a,b}∈ E(T ) in the treeT
Set xi(t + 1) to an arbitrarily chosen element ofχ(bi(t + 1))∩HG i . Since thebi(·) values are updated using the algorithmA, these values converge onto a single edge{a,b}∈ E(T ) in the treeT. Asχ(a)∪χ(b) is a clique due to the expandedness ofT, the output valuesx(·) will have ...
-
[19]
send messages to other processors in the system,
-
[20]
receive messages from all other processors (or no message from a faulty processor),
-
[21]
6.2 Upper bound for convex consensus We start with the positive result given by Theorem 7
update local state based on received messages. 6.2 Upper bound for convex consensus We start with the positive result given by Theorem 7. The algorithm follows the same idea as the Vaidya–Garg algorithm for Euclidean spaces [46, 54]. For the sake of completeness, we reiterate ...
-
[22]
µ(x,y )⁄=x for allx⁄=y
-
[23]
Theorem 12
y /∈⟨A\µ(x,y )⟩ for allx⁄=y. Theorem 12. Suppose there exists anm-blocking instance(A,µ ) forC. Ifn≤ (m + 1)f, then there does not exist anf-resilient algorithm which outputsY ⊊⟨X⟩ for all input setsX∈ (V m ) . Proof. For the sake of contradiction, suppose there exists an algo...
-
[24]
Nevertheless, we have seen that on chordal graphs and cycle-free semilattices we can solve approximate agreement efficiently
It seems difficult to come up with a general rule for the output mapφ :C →V in a way that guarantees that the convex hull of active values shrinks. Nevertheless, we have seen that on chordal graphs and cycle-free semilattices we can solve approximate agreement efficiently. In both...
-
[25]
It is unclear whether the abstract approximate agreement problem can be solved on general convexity spaces. For example, the asynchronous algorithms for approximate agreement on graphs presented here fail for non-chordal graphs: already the simplest example of a non-chordal gr...
-
[26]
However, our positive results for the asynchronous model hold in cases where the Carathéodory number is at most two
We obtained resilience lower bounds in terms of the Carathéodory and the Helly num- bers. However, our positive results for the asynchronous model hold in cases where the Carathéodory number is at most two. Interestingly, in the continuous setting of multidimen- sional approxi...
2018
-
[27]
Optimal resilience asynchronous approx- imate agreement
Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approx- imate agreement. InProc. International Conference on Principles of Distributed Systems (OPODIS 2015), pages 229–239, 2005.doi:10.1007/11516798_17
2015 doi
-
[28]
Adaptive and efficient algorithms for lattice agreement and renaming
Hagit Attiya and Arie Fouren. Adaptive and efficient algorithms for lattice agreement and renaming. SIAM Journal on Computing, 31(2):642–664, 2001
2001
-
[29]
Atomic snapshots using lattice agree- ment
Hagit Attiya, Maurice Herlihy, and Ophir Rachman. Atomic snapshots using lattice agree- ment. Distributed Computing, 8(3):121–132, 1995
1995
-
[30]
Rommel M Barbosa, Erika M. M. Coelho, Mitre C. Dourado, Dieter Rautenbach, and Jayme L. Szwarcfiter. On the carathéodory number for the convexity of paths of order three. SIAM Journal on Discrete Mathematics, 26(3):929–939, 2012
2012
-
[31]
A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph.Information Processing Letters, 111:508–511, 2011
Anne Berry and Romain Pogorelcnik. A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph.Information Processing Letters, 111:508–511, 2011. 21
2011
-
[32]
Easy impossibility proofs fork-set agreement in message passing systems
Martin Biely, Peter Robinson, and Ulrich Schmid. Easy impossibility proofs fork-set agreement in message passing systems. InProc. International Conference on Principles of Distributed Systems (OPODIS 2011), pages 299–312. Springer, 2011
2011
-
[33]
Jean R. S. Blair and Barry Peyton. An introduction to chordal graphs and clique trees. In Alan George, John R. Gilbert, and Joseph W. H. Liu, editors,Graph Theory and Sparse Matrix Computation, pages 1–29. Springer, Heidelberg, 1993
1993
-
[34]
More choices allow more faults: Set consensus problems in totally asynchronous systems
Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132–158, 1993
1993
-
[35]
Onk-set consensus problems in asynchronous systems
Roberto De Prisco, Dahlia Malkhi, and Michael Reiter. Onk-set consensus problems in asynchronous systems. IEEE Transactions on Parallel and Distributed Systems, 12(1):7–21, 2001
2001
-
[36]
Graph Theory
Reinhard Diestel. Graph Theory. Springer, Heidelberg, 4th edition, 2010
2010
-
[37]
Dietrich
Brenda L. Dietrich. Matroids and antimatroids – a survey.Discrete Mathematics, 78(3):223– 237, 1989
1989
-
[38]
On rigid circuit graphs
Gabriel Andrew Dirac. On rigid circuit graphs. InAbhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 25, pages 71–76. Springer, 1961
1961
-
[39]
Fault-tolerant algorithms for tick-generation in asynchronous logic.Journal of the ACM, 61(5):30:1–30:74,
Danny Dolev, Matthias Függer, Christoph Lenzen, and Ulrich Schmid. Fault-tolerant algorithms for tick-generation in asynchronous logic.Journal of the ACM, 61(5):30:1–30:74,
-
[40]
Lynch, Shlomit S
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
1986
-
[41]
Shlomi Dolev and Jennifer L. Welch. Self-stabilizing clock synchronization in the presence of Byzantine faults.Journal of the ACM, 51(5):780–799, 2004.doi:10.1145/1017460.1017463
2004
-
[42]
Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp M
Mitre C. Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp M. Schäfer, and Jayme L. Szwarcfiter. On the Carathéodory number of interval and graph convexities. Theoretical Computer Science, 510:127–135, 2013.doi:10.1016/j.tcs.2013.09.004
2013 doi
-
[43]
Convexity in combinatorial structures
Pierre Duchet. Convexity in combinatorial structures. InProc. Winter School on Abstract Analysis, pages 261–293. Circolo Matematico di Palermo, 1987
1987
-
[44]
Convex sets in graphs, II
Pierre Duchet. Convex sets in graphs, II. Minimal path convexity.Journal of Combinatorial Theory, Series B, 44(3):307–316, 1988.doi:10.1016/0095-8956(88)90039-1
1988 doi
-
[45]
Helly, Radon, and Carathéodory type theorems
Jürgen Eckhoff. Helly, Radon, and Carathéodory type theorems. InHandbook of Convex Geometry, Part A, pages 389–448. Elsevier Science Publishers B.V, 1993
1993
-
[46]
Edelman and Robert E
Paul H. Edelman and Robert E. Jamison. The theory of convex geometries.Geometriae Dedicata, 19(3):247–270, 1985.doi:10.1007/BF00149365
1985 doi
-
[47]
Edelman and Michael E
Paul H. Edelman and Michael E. Saks. Combinatorial representation and convex dimension of convex geometries.Order, 5(1):23–32, 1988.doi:10.1007/BF00143895
1988 doi
-
[48]
Faleiro, Sriram Rajamani, Kaushik Rajan, G
Jose M. Faleiro, Sriram Rajamani, Kaushik Rajan, G. Ramalingam, and Kapil Vaswani. Generalized lattice agreement. In Proc. ACM Symposium on Principles of Distributed Computing (PODC 2012), pages 125–134. ACM, 2012.doi:10.1145/2332432.2332458. 22
2012
-
[49]
Farber and R
M. Farber and R. E. Jamison. Convexity in graphs and hypergraphs.SIAM Journal on Algebraic Discrete Methods, 7(3):433–444, 1986
1986
-
[50]
Martin Farber and Robert E. Jamison. On local convexity in graphs.Discrete Mathematics, 66(3):231–247, 1987.doi:10.1016/0012-365X(87)90099-9
1987 doi
-
[51]
Asymptotically optimal algorithms for approximate agreement.Distrib- uted Computing, 4(1):9–29, 1990
Alan David Fekete. Asymptotically optimal algorithms for approximate agreement.Distrib- uted Computing, 4(1):9–29, 1990
1990
-
[52]
Asynchronous approximate agreement.Information and Computation, 115(1):95–124, 1994
Alan David Fekete. Asynchronous approximate agreement.Information and Computation, 115(1):95–124, 1994
1994
-
[53]
Fischer, Nancy A
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process.Journal of the ACM, 32(2):374–382, 1985.doi:10.1145/ 3149.214121
1985
-
[54]
Eli Gafni and Petr Kuznetsov.N-consensus is the second strongest object forN +1 processes. In Proc. International Conference on Principles of Distributed Systems (OPODIS 2007), pages 260–273. Springer, Heidelberg, 2007
2007
-
[55]
Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.SIAM Journal on Computing, 1(2):180–187, 1972
Fănică Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph.SIAM Journal on Computing, 1(2):180–187, 1972
1972
-
[56]
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2013
Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum.Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2013
2013
-
[57]
A classification of wait-free loop agreement tasks
Maurice Herlihy and Sergio Rajsbaum. A classification of wait-free loop agreement tasks. Theoretical Computer Science, 291(1):55–77, 2003
2003
-
[58]
Maurice Herlihy, Sergio Rajsbaum, and Mark R. Tuttle. Unifying synchronous and asyn- chronous message-passing models. InProc. ACM Symposium on Principles of Distributed Computing (PODC 1998), pages 133–142. ACM, 1998
1998
-
[59]
Jamison and Richard Nowakowski
Robert E. Jamison and Richard Nowakowski. A Helly theorem for convexity in graphs. Discrete Mathematics, 51(1):35–39, 1984.doi:10.1016/0012-365X(84)90021-9
1984 doi
-
[60]
A perspective on abstract convexity: classifying alignments by varieties
Robert E Jamison-Waldner. A perspective on abstract convexity: classifying alignments by varieties. Convexity and Related Combinatorial Geometry, New York, 1982
1982
-
[61]
Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers.Pacific Journal of Mathematics, 38(2):471–485, 1971
David Kay and Eugene W Womble. Axiomatic convexity theory and relationships between the Carathéodory, Helly, and Radon numbers.Pacific Journal of Mathematics, 38(2):471–485, 1971
1971
-
[62]
Brief announcement: Distributed minimum vertex coloring and maximum independent set in chordal graphs
Christian Konrad and Viktor Zamaraev. Brief announcement: Distributed minimum vertex coloring and maximum independent set in chordal graphs. InProc. ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 159–161, New York, NY, USA,
2018
-
[64]
Greedoids – A structural framework for the greedy algorithm
Bernhard Korte and László Lovász. Greedoids – A structural framework for the greedy algorithm. InProgress in Combinatorial Optimization, pages 221–243. Academic Press, 1984. doi:10.1016/B978-0-12-566780-7.50019-2
1984 doi
-
[65]
Springer Science & Business Media, 2012
Bernhard Korte, László Lovász, and Rainer Schrader.Greedoids, volume 4. Springer Science & Business Media, 2012. 23
2012
-
[66]
Lauritzen.Graphical models, volume 17
Steffen L. Lauritzen.Graphical models, volume 17. Clarendon Press, 1996
1996
-
[67]
Near-optimal self-stabilising counting and firing squads
Christoph Lenzen and Joel Rybicki. Near-optimal self-stabilising counting and firing squads. Distributed Computing, 2018. doi:10.1007/s00446-018-0342-6
2018 doi
-
[68]
Self-stabilising Byzantine clock synchronisation is almost as easy as consensus.Journal of the ACM, 2019
Christoph Lenzen and Joel Rybicki. Self-stabilising Byzantine clock synchronisation is almost as easy as consensus.Journal of the ACM, 2019. To appear
2019
-
[69]
Classifying rendezvous tasks of arbitrary dimension
Xingwu Liu, Zhiwei Xu, and Jianzhong Pan. Classifying rendezvous tasks of arbitrary dimension. Theoretical Computer Science, 410(21):2162 – 2173, 2009.doi:10.1016/j.tcs. 2009.01.033
2009 doi
-
[70]
Communication complexity and combinatorial lattice theory
László Lovăsz and Michael Saks. Communication complexity and combinatorial lattice theory. Journal of Computer and System Sciences, 47(2):322–349, 1993
1993
-
[71]
Tze-Heng Ma and Jeremy P. Spinrad. Cycle-free partial orders and chordal comparability graphs. Order, 8(1):49–61, Mar 1991.doi:10.1007/BF00385814
1991 doi
-
[72]
Multidimensional approximate agreement in Byzantine asynchronous systems.Proc
Hammurabi Mendes and Maurice Herlihy. Multidimensional approximate agreement in Byzantine asynchronous systems.Proc. Annual ACM symposium on Symposium on Theory of Computing (STOC 2013), page 391, 2013.doi:10.1145/2488608.2488657
2013
-
[73]
Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in Byzantine systems.Distributed Computing, 28:423–441, 2015
2015
-
[74]
Nielsen and Ortrud R
Morten H. Nielsen and Ortrud R. Oellermann. Steiner trees and convex geometries.SIAM Journal on Discrete Mathematics, 23(2):680–693, 2009
2009
-
[75]
Pease, Robert E
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
1980
-
[76]
Ignacio M. Pelayo. Geodesic Convexity in Graphs. Springer, 2013. doi:10.1007/ 978-1-4614-8699-2
2013
-
[77]
Convexities on ordered structures have their Krein–Milman theorem.Journal of Convex Analysis, 21(1):89–120, 2014
Paul Poncet. Convexities on ordered structures have their Krein–Milman theorem.Journal of Convex Analysis, 21(1):89–120, 2014
2014
-
[78]
Donald J. Rose. Triangulated graphs and the elimination process.Journal of Mathematical Analysis and Applications, 32(3):597–609, 1970
1970
-
[79]
Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs.SIAM Journal on computing, 5(2):266–283, 1976
1976
-
[80]
Simulating authenticated broadcasts to derive simple fault- tolerant algorithms
TK Srikanth and Sam Toueg. Simulating authenticated broadcasts to derive simple fault- tolerant algorithms. Distributed Computing, 2(2):80–94, 1987
1987
-
[81]
Vaidya and Vijay K
Nitin H. Vaidya and Vijay K. Garg. Byzantine vector consensus in complete graphs. InProc. ACM Symposium on Principles of Distributed Computing (PODC 2013), pages 65–73, 2013
2013
-
[82]
Elsevier, 1993
Marcel LJ van De Vel.Theory of convex structures, volume 50. Elsevier, 1993
1993
-
[83]
Chordal graphs and semidefinite optimization
Lieven Vandenberghe and Martin S Andersen. Chordal graphs and semidefinite optimization. Foundations and Trends in Optimization, 1(4):241–433, 2015
2015
-
[84]
A new fault-tolerant algorithm for clock synchronization
Jennifer Lundelius Welch and Nancy Lynch. A new fault-tolerant algorithm for clock synchronization. Information and Computation, 77(1):1–36, 1988. 24
1988
-
[85]
Xiong Zheng, Changyong Hu, and Vijay K. Garg. Lattice agreement in message passing systems. In Proc. International Symposium on Distributed Computing (DISC 2018), volume 121 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 41:1–41:17, Dagstuhl, Germany, 2018....
2018 doi
-
[2018]
doi:10.1145/3212734.3212787
ACM. doi:10.1145/3212734.3212787
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.