{"id":"16cd78cf-a8eb-4121-85ed-1cd82d76fb11","arxiv_id":"1908.02743","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Byzantine approximate agreement on chordal graphs and cycle-free semilattices is solvable in O(log N) asynchronous rounds when n > (ω+1)f, and synchronous exact convex consensus has tight resilience Θ(f).","lead":"This paper develops algorithms and impossibility results for Byzantine fault-tolerant approximate agreement when input values are vertices of a graph or elements of a semilattice, instead of real numbers. It shows that chordal graphs admit efficient asynchronous agreement when the number of processors exceeds a graph-parameter threshold times the number of faults.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 15 is false for a 5-element convexity space (and the proof's contradiction is invalid), so the advertised general asynchronous impossibility result, Theorem 11's first bullet, is unsupported as stated.","rationale":"The reader's weakest_assumption is correct, and I agree that it is the most load-bearing concern. The main upper-bound algorithms (Theorems 2, 3, and 4) have self-contained arguments that do not invoke Lemma 15: the Helly-number argument in Lemma 1, the tree diameter-halving argument, and the clique-tree feasibility lemmas stand independently. However, the paper explicitly lists 'general impossibility results for asynchronous systems' among its contributions, and Theorem 11's first bullet is the advertised Carathéodory-number lower bound for arbitrary convexity spaces. That result is exactly what Lemma 16 feeds. Since Lemma 15 is false (not merely unproved) for an irredundant set in a finite convexity space, the proof as written does not establish the theorem. This is a concrete correctness risk, not a disagreement with the surrounding consensus: the theorem might be true or repairable, but the argument has a specific gap. My concrete test settles the concern by exposing the failed lemma on an explicit 5-element closed family. The graph-specific lower bound is not affected because for diameter-at-least-two graphs the needed blocking instances can be built from size-2 irredundant nonedges or from free cliques, avoiding Lemma 15; the semilattice corollary should be re-proved with a direct argument or explicitly exempted from the flawed lemma. Since the constructive contributions remain plausible and the affected general theorem is localizable, the appropriate disposition is to keep the reader's CONDITIONAL verdict rather than reject the paper.","tokens_in":21508,"tokens_out":21267,"duration_ms":226029,"concrete_test":"Independently instantiate the blocking construction on the 5-element space above: enumerate the convexity space as the intersection-closure of {V,∅,{0,1,2},{0,1,4},{2,4},{0,1},{2},{4}} and verify that ⟨{0,2,4}⟩=V, ⟨{0,4}⟩={0,1,4}, ⟨{0,2}⟩={0,1,2}, and that for x=0, y=1 no admissible µ(x,y)∈A∖{x} satisfies y∉⟨A∖µ⟩. If Theorem 12 cannot be rerun with a different blocking instance, either repair Lemma 15 (e.g., restrict its use to settings where a direct proof exists, such as |A|=2 for graphs) or restate Theorem 11's first bullet as unproven for general convexity spaces.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 15's proof argues that y∈B contradicts y∈⟨A⟩∖A via ∂A⊆⟨A⟩∖A; but y∉∂A does not imply y∉⟨A⟩∖A, so the contradiction is invalid. The lemma is actually false, even for an irredundant set. Take 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}, we have ⟨A⟩=V, ⟨A∖{2}⟩={0,1,4}, and ⟨A∖{4}⟩={0,1,2}; also A is irredundant because 3∈∂A=V∖(⟨{2,4}⟩∪⟨{0,4}⟩∪⟨{0,2}⟩). For a=0 and y=1∈⟨A⟩∖A, both candidate b∈A∖{0} give y∈⟨A∖b⟩, so no such b exists. Consequently Lemma 16 cannot define the required blocking map µ for this irredundant 3-set, and the proof of Theorem 11's first bullet collapses for arbitrary convexity spaces. The chordal-graph and semilattice upper bounds and the synchronous lower bounds do not depend on this lemma; graph lower bounds can instead use size-2 irredundant sets or free cliques directly.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21833,"tokens_out":40650,"duration_ms":453145,"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":[{"comment":"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.","section":"7.2, Lemma 15"},{"comment":"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.","section":"4.1, Lemmas 6 and 7"}],"minor_comments":[{"comment":"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.","section":"4.2, Theorem 3"},{"comment":"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.","section":"4.1, Theorem 2"},{"comment":"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.","section":"2.1"}],"recommendation":"major_revision","confidential_remarks":"The false lemma is isolated to the general lower-bound section; the positive algorithms and the synchronous lower bounds appear worth publishing. I recommend requesting a revision in which the authors either prove a corrected version of Theorem 11 under additional hypotheses or explicitly restrict the claim to settings where blocking instances are known to exist. The tree-convergence proofs also need a careful rewrite, but I do not see grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper lifts Mendes–Herlihy approximate agreement from Euclidean space into abstract convexity spaces, and the graph and semilattice applications are genuinely new. The main constructive results hold up. The chordal-graph algorithm via expanded clique trees is a real contribution, and the cycle-free semilattice Byzantine agreement is the first I know of. The synchronous convex consensus upper and lower bounds also look correct and are cleanly argued.\n\nThe trouble is in Section 7. Lemma 15 claims that in any convexity space, for an irredundant set A and any y in <A>\\A, there is some b in A\\{a} with y not in <A\\b>. The proof uses the line “y in B implies y not in dA subset <A>\\A”, but the inclusion points the wrong way. And the lemma is actually false: there is a 5-element convexity space (V={0,1,2,3,4}, convex sets ∅, V, {0,1}, {2}, {4}, {0,1,2}, {0,1,4}, {2,4}) where A={0,2,4} is irredundant, y=1 is in <A>\\A, but both candidate b's keep y in the smaller hull. So Lemma 16 cannot build the blocking map, and Theorem 11's first bullet (the n≤(c+1)f impossibility for arbitrary convexity spaces) is unsupported as stated.\n\nThis does not sink the paper's main results: the chordal graph and semilattice upper bounds do not depend on Lemma 15, and the synchronous lower bounds use free sets, not this lemma. The specific graph/semilattice corollaries from Theorem 11 probably survive with a more direct proof, but the paper should either repair the lemma or restrict the theorem to settings where it provably holds (e.g., convex geometries with Carathéodory number 2, or lattices). Right now the abstract advertises a general impossibility result that the body does not actually prove.\n\nWho should read this: distributed systems people working on approximate agreement, and anyone interested in combinatorial convexity in fault-tolerance. It deserves a serious referee — the core algorithms are valuable and the flaw is localised. I'd accept it with major revision, but I'd want the authors to fix the lemma or clearly delimit the scope of Theorem 11 before publication.","headline":"Solid algorithms for chordal graphs and cycle-free semilattices, but the general asynchronous impossibility theorem rests on a false lemma and needs repair.","tokens_in":22321,"tokens_out":3716,"would_cite":true,"duration_ms":35698,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68M14","68W15","05C85","05C17"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["approximate agreement","Byzantine faults","chordal graphs","abstract convexity","lattice agreement","convex consensus","Helly number","Carathéodory number"],"falsifier":"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.","tokens_in":21315,"feed_emoji":"🕸️","tokens_out":13188,"duration_ms":125983,"temperature":0.7,"pith_summary":"This paper extends the classical task of approximate agreement, in which processors must output values that are close to one another while staying in the convex hull of the correct inputs, from Euclidean spaces to discrete value sets modelled by graphs and semilattices. Its central result is that on any chordal graph $G$, Byzantine-faulty processors can solve monophonic approximate agreement in $O(\\log |V|)$ asynchronous rounds whenever $n>(\\omega(G)+1)f$ of the $n$ processors are non-faulty, where $\\omega(G)$ is the largest clique size; the outputs land in a clique of diameter at most one inside the chordless-path convex hull of the correct inputs. The same framework yields the first Byzantine-tolerant lattice-agreement algorithm, for cycle-free semilattices, and tight synchronous bounds for exact convex consensus on any convexity space with Helly number $\\omega$. The paper also derives resilience lower bounds from the Carathéodory and Helly numbers, suggesting that these combinatorial invariants, not Euclidean dimension, set the threshold for discrete agreement.","feed_headline":"Processors can nearly agree on chordal graphs in O(log V) rounds","feed_subtitle":"New algorithm resists Byzantine faults when n>(omega+1)f and keeps outputs inside a clique of the input hull.","key_machinery":"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.","core_discovery":"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\\}$.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Establishes the monophonic (chordless path) convexity for graphs and its Carathéodory number at most two.","marker":"[18]"},{"why":"Supplies the Helly theorem for graph convexity that identifies the Helly number with the clique number.","marker":"[33]"},{"why":"Shows chordal graphs are exactly the graphs whose monophonic convexity is a convex geometry and that geodesic and monophonic convexities coincide on Ptolemaic graphs.","marker":"[23]"},{"why":"Gives the iterative intersection-of-hulls Byzantine algorithm and the Euclidean threshold that this paper generalises to discrete convexity spaces.","marker":"[46]"},{"why":"Provides the theory of convex geometries, including extreme-point characterisation, convex elimination orders, and the equality of Helly number with maximum free-set size.","marker":"[20]"},{"why":"Supplies the algebraic convexity facts for semilattices: free sets are exactly chains and the Helly number is the height.","marker":"[50]"},{"why":"Defines cycle-free partial orders via chordal comparability graphs, the structural class on which the lattice-agreement algorithm relies.","marker":"[44]"},{"why":"Provides the synchronous multivalued Byzantine agreement subroutine used by the convex-consensus upper bound.","marker":"[53]"},{"why":"Gives the reliable broadcast that simulates the Byzantine asynchronous round model used by the iterative algorithms.","marker":"[1]"}],"fun_headline_variants":["Byzantine-safe approximate agreement on chordal graphs","Clique-convergent agreement on chordal graphs despite faults","Resilient graph agreement: clique-bound outputs in log rounds","Fault-tolerant graph consensus on chordal convexity spaces"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Byzantine-safe approximate agreement on chordal graphs","Clique-convergent agreement on chordal graphs despite faults","Resilient graph agreement: clique-bound outputs in log rounds","Fault-tolerant graph consensus on chordal convexity spaces"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000326,"raw_usage":{"total_tokens":1883,"prompt_tokens":1063,"completion_tokens":820,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":679,"completion_tokens_details":{"reasoning_tokens":752}},"tokens_in":679,"tokens_out":820,"duration_ms":8259,"temperature":1.0,"reasoning_tokens":752,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:43:27.834131+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Since thebi(·) values are updated using the algorithmA, these values converge onto a single edge{a,b}∈ E(T ) in the treeT","cited_arxiv_id":null,"evidence_quote":"Establishes the monophonic (chordless path) convexity for graphs and its Carathéodory number at most two."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Helly theorem for graph convexity that identifies the Helly number with the clique number."},{"cited_title":"Theorem 12","cited_arxiv_id":null,"evidence_quote":"Shows chordal graphs are exactly the graphs whose monophonic convexity is a convex geometry and that geodesic and monophonic convexities coincide on Ptolemaic graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the theory of convex geometries, including extreme-point characterisation, convex elimination orders, and the equality of Helly number with maximum free-set size."},{"cited_title":"Convex sets in graphs, II","cited_arxiv_id":null,"evidence_quote":"Defines cycle-free partial orders via chordal comparability graphs, the structural class on which the lattice-agreement algorithm relies."}],"review_version":1}