Pith. sign in

REVIEW 2 major objections 1 cited by

A synchronous protocol achieves optimal resilience for approximate agreement on trees with round complexity O(log D(T)/log log D(T)).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Optimal round complexity and resilience approximate agreement on trees with matching lower bounds, extended to block graphs in synchronous and asynchronous models.

T0 review reviewed 2026-05-23 challenge →

load-bearing objection The paper gives an asymptotically optimal synchronous protocol for approximate agreement on trees plus a lower bound extension to general graphs, with the extension needing close verification on whether it preserves the exact convex hull and 1-close conditions. the 2 major comments →

arxiv 2502.05591 v5 pith:3YJDDNEG submitted 2025-02-08 cs.DC

Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs

Marc Fuchs , Diana Ghinea , Zahra Parsaeian , Joel Rybicki This is my paper
classification cs.DC
keywords approximate agreementByzantine faultstreesblock graphsround complexityresiliencesynchronous protocolsdistributed computing
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

The paper constructs a synchronous protocol allowing parties with vertices on a known tree to output 1-close vertices inside the convex hull of honest inputs despite Byzantine faults. The protocol matches optimal resilience and requires only O(log D(T)/log log D(T)) rounds where D(T) is the tree diameter. It pairs this with a lower bound of Omega(log D(G)/log log D(G) + log (n+t)/t) rounds that holds for approximate agreement on any graph G. The bounds match asymptotically whenever the number of faults t is linear in the total number of parties n, closing an open question on extending real-valued approximate agreement to structured input spaces.

Core claim

We present a synchronous protocol with optimal resilience and round complexity O(log D(T)/log log D(T)) for approximate agreement on trees. We extend impossibility results for real-valued approximate agreement to any graph G by proving a lower bound of Omega(log D(G)/log log D(G) + log (n+t)/t) rounds. Together these establish asymptotic optimality whenever t is Theta(n). The same techniques yield protocols for block graphs with optimal resilience in both synchronous and asynchronous models and optimal round complexity in the synchronous model.

What carries the argument

The diameter-driven synchronous protocol that recursively coordinates on substructures of the tree while preserving convex-hull and 1-closeness invariants, together with the direct extension of real-valued impossibility arguments to arbitrary graphs.

Load-bearing premise

Lower-bound techniques that work for real numbers extend to trees and graphs while preserving the convex-hull and 1-close output requirements.

What would settle it

A concrete synchronous protocol for a tree of diameter D that terminates in o(log D / log log D) rounds with optimal resilience, or a counter-example graph where the stated lower bound fails under the convex-hull and 1-close conditions, would refute the optimality claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Optimal-resilience protocols exist for block graphs in both synchronous and asynchronous models.
  • Round complexity remains optimal for block graphs in the synchronous model.
  • The lower bound applies to approximate agreement on every graph.
  • Asymptotic optimality holds for any graph whenever the fault fraction is constant.

Where Pith is reading between the lines

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

  • The same reduction technique may yield efficient protocols on other graphs with bounded treewidth or hierarchical structure.
  • The diameter dependence suggests that input spaces with small metric diameter admit faster agreement even under faults.
  • These bounds could guide the design of fault-tolerant coordination primitives on network topologies that are themselves trees or block graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 0 minor

Summary. The paper claims a synchronous protocol for approximate agreement (AA) on trees with optimal resilience and round complexity O(log D(T)/log log D(T)), where parties output 1-close vertices in the convex hull of honest inputs. It extends real-valued AA impossibility results to arbitrary graphs G, proving an Omega(log D(G)/log log D(G) + log((n+t)/t)) lower bound, establishing asymptotic optimality when t=Theta(n). The techniques are further extended to block graphs, yielding optimal-resilience protocols in both synchronous and asynchronous models with optimal synchronous round complexity.

Significance. If the central claims hold, the work resolves open questions on round complexity and resilience for synchronous AA beyond real lines, providing the first optimal results for trees and block graphs. The matching upper and lower bounds (when t=Theta(n)) and the extension to block graphs for both models are notable strengths, as is the explicit construction of a protocol achieving the stated complexity.

major comments (2)
  1. [Abstract] Abstract (lower bound paragraph): the claimed extension of real-valued AA impossibility results to arbitrary graphs G must be shown to preserve both the convex-hull containment and the 1-close output requirements exactly as used in the tree protocol; if the proof relaxes either condition or alters the diameter-based adversary argument when generalizing from paths, the lower bound no longer matches the upper-bound problem and the asymptotic optimality claim (when t=Theta(n)) does not follow.
  2. [Abstract] The lower-bound statement includes an additive log((n+t)/t) term; the manuscript must clarify whether this term is necessary for the graph case or whether it can be absorbed into the log D(G)/log log D(G) term under the same convex-hull and 1-close conditions used for the tree upper bound.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for identifying points that require clarification. Both major comments concern the lower-bound argument and its presentation; we address them directly below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (lower bound paragraph): the claimed extension of real-valued AA impossibility results to arbitrary graphs G must be shown to preserve both the convex-hull containment and the 1-close output requirements exactly as used in the tree protocol; if the proof relaxes either condition or alters the diameter-based adversary argument when generalizing from paths, the lower bound no longer matches the upper-bound problem and the asymptotic optimality claim (when t=Theta(n)) does not follow.

    Authors: The lower-bound proof (Section 5) reduces from the real-valued impossibility while embedding the path instance into an arbitrary graph G such that the convex hull of honest inputs is exactly preserved under the graph metric and the output requirement remains that every honest party outputs a vertex at distance at most 1 from some vertex in that hull. The adversary construction is diameter-based and identical in structure to the path case; no relaxation occurs. We will add an explicit sentence in the abstract and a short paragraph at the beginning of Section 5 stating this preservation. revision: yes

  2. Referee: [Abstract] The lower-bound statement includes an additive log((n+t)/t) term; the manuscript must clarify whether this term is necessary for the graph case or whether it can be absorbed into the log D(G)/log log D(G) term under the same convex-hull and 1-close conditions used for the tree upper bound.

    Authors: The stated lower bound is already in fractional form: Ω(log D(G) / (log log D(G) + log((n+t)/t))). This is the direct generalization of the known real-valued bound; the additive term in the denominator is necessary in general (it cannot be absorbed when t = o(n)). When t = Θ(n) the extra term is O(1) and the bound simplifies to Ω(log D(G)/log log D(G)), matching the upper bound asymptotically under the same convex-hull and 1-close conditions. We will insert a clarifying sentence immediately after the lower-bound statement in the abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper constructs a new synchronous protocol for AA on trees with O(log D(T)/log log D(T)) rounds and optimal resilience, then separately extends prior real-valued impossibility results to graphs G with a matching lower bound. No equations or steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations. The lower-bound extension is presented as building on external real-valued AA results rather than re-deriving them from the protocol itself. The central optimality claim when t=Θ(n) rests on independent upper- and lower-bound arguments that do not collapse into each other.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The central claims rest on standard domain assumptions from distributed computing theory; no free parameters or new invented entities are apparent from the abstract.

axioms (3)
  • domain assumption Synchronous communication model with bounded message delays.
    Invoked for the round complexity analysis in synchronous AA.
  • domain assumption Byzantine fault model where up to t parties can deviate arbitrarily.
    Core assumption for resilience claims.
  • domain assumption Inputs are vertices on a publicly known tree T with outputs required to be 1-close in the convex hull of honest inputs.
    Defines the problem setting for trees and block graphs.

reviewed 2026-05-23 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs." pith.science (2026). https://pith.science/paper/3YJDDNEG

@misc{pith2026250205591,
  author       = {Pith},
  title        = {Pith review of: Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3YJDDNEG}},
  note         = {Machine review of arXiv:2502.05591}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Approximate Agreement ($\mathcal{AA}$) is a fundamental primitive that, even in the presence of Byzantine faults, allows honest parties to obtain close (but not necessarily identical) outputs that lie within the range of their inputs. While the optimal round complexity of synchronous $\mathcal{AA}$ on real values is well understood, its extension to other input spaces has remained open, with fundamental questions regarding achievable resilience and round efficiency still unresolved. In this work, we investigate the optimal round complexity of synchronous $\mathcal{AA}$ on trees under Byzantine failures. In this setting, parties hold as inputs vertices of a publicly known labeled tree $T$ and must output $1$-close vertices lying in the convex hull of the honest inputs. We present a synchronous protocol with optimal resilience and round complexity $O\left(\frac{\log D(T)}{\log \log D(T)}\right)$, where $D(T)$ denotes the diameter of the input space tree. Complementing this result, we extend impossibility results for real-valued $\mathcal{AA}$ to any graph $G$ by proving a lower bound of $\Omega\left(\frac{\log D(G)}{\log \log D(G) + \log \frac{n+t}{t}}\right)$ rounds, where $n$ is the number of parties and $t$ the number of Byzantine faults. Together, these results establish the asymptotic optimality of our protocol whenever $t \in \Theta(n)$. We further extend our techniques to block graphs by leveraging their clique tree structure. This yields protocols for $\mathcal{AA}$ on block graphs with optimal resilience in both the synchronous and asynchronous models, and with optimal round complexity in the synchronous model.

Figures

Figures reproduced from arXiv: 2502.05591 by Diana Ghinea, Joel Rybicki, Marc Fuchs, Zahra Parsaeian.

Figure 1
Figure 1. Figure 1: In this tree, the convex hull of {u1, u2, u3} is the set of vertices {u1, u2, u3, u4, u5}. We may now recall the definition of AA on trees, as presented in [35]. Definition 2. Consider a labeled tree T, and let Π be an n-party protocol in which every party holds a vertex of T as input. We say that Π achieves AA if the following properties hold even when up to t of the n parties involved are corrupted: • Te… view at source ↗
Figure 2
Figure 2. Figure 2: Let P be the assumed path, represented by the sequence of vertices v1, v2, . . . , v8. The vertices u1, u2, u3 correspond to the honest inputs, whose convex hull is highlighted in green. The projections of u1, u2, u3 onto path P are vertices v3, v4, v6 respectively. Afterwards, as described in Section 4, the parties denote the k vertices in path P by (v1, v2, . . . , vk), where v1 is the endpoint with the … view at source ↗
Figure 3
Figure 3. Figure 3: An input space tree [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Vertices v4, v8 are not valid, but are in the subtree of a valid vertex (with respect to root v1). We note that this does not imply that the vertices LclosestInt(j) are valid. Consider again the input space tree in [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: In this figure, vertices u1, u2, u3 are the honest inputs, and the highlighted paths (v1, v2, . . . , v6) and (v1, v2, . . . , v7) represent the paths P that the honest parties obtained via PathsFinder. Note that an honest party p that holds P = (v1, . . . , v6) might obtain a value j such that closestInt(j) = 7, and p does not know whether v7 should be the actual vertex v7 or the red vertex adjacent to v6… view at source ↗
Figure 6
Figure 6. Figure 6: An honest party p may hold a path Q such as (v1, . . . , v7). Moreover, all honest parties’ paths P are guaranteed to be prefixes of p’s path Q, such as those highlighted in cyan and light cyan: (v1, v2, v3), and (v1, v2, . . . v5). Note that the honest parties’ paths P intersect the honest input’s convex hull ⟨u1, u2, u3⟩. Finally, each party p outputs the vertex vclosestInt(j) on its path Q: note that cl… view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. General Convex Agreement with Near-Optimal Communication

    cs.DC 2026-02 reject novelty 7.0

    New deterministic CA protocols achieve near-optimal communication for finite convexity spaces and R^d using extractor-based committee assignment.

This paper was first reviewed by grok-4.3 on May 23, 2026.