Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read Synchronous approximate agreement on any input tree T can be solved in O(log D(T)/log log D(T)) rounds with optimal Byzantine resilience, and this is asymptotically tight when the number of faults is a constant fraction of parties.

desk verdict The tree protocol is a real and likely correct contribution, but the abstract promises block graph results that are not in the paper, and Fekete's bound is misquoted in a way that needs a small fix. read the letter →

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

Marc Fuchs , Diana Ghinea , Zahra Parsaeian , Joel Rybicki This is my paper · ORCID
classification cs.DC MSC 68M1468W1505C05
keywords approximateagreementByzantinefaultsroundcomplexitytreesblockgraphsgradedbroadcastsynchronousdistributedsystemsconvexhull
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper settles the round complexity of Byzantine-resilient approximate agreement when the input space is a tree: parties hold vertices of a known tree, and for any prescribed closeness they must output vertices within distance one of each other that lie in the convex hull of honest inputs. The paper proves a synchronous protocol that solves the problem in $O(\log D(T)/\log\log D(T))$ communication rounds, where $D(T)$ is the diameter of the input tree, tolerating up to $t

What carries the argument

The load-bearing object is a two-path prefix constructor built from graded broadcast, a three-round primitive in which honest senders' messages are delivered with grade 2 to everyone and any two positive grades imply the same message. Each party sends the path from a fixed root to its input vertex through a graded broadcast; every honest party then sets $P$ to the longest path prefix supported by $n-t$ grade-2 messages and $Q$ to the longest prefix supported by $n-t$ grade-at-least-1 messages. These guarantees imply that every honest $P$ is a prefix of every honest $Q$, and that $P$ intersects the convex hull of honest inputs. The parties then project their input vertices onto their own $P$, feed the resulting integer positions into a gradecast-based real-valued approximate-agreement protocol with error $1$, and output the vertex whose position in $Q$ is closest to the returned real value. A Euler-tour list construction supports an intermediate protocol with $O(\log|V(T)|/\log\log|V(T)|)$ rounds, while the lower bound uses a chain of views whose consecutive entries force honest outputs at least $D(T)/s$ apart.

What would settle it

Run the described protocol with $t=\lfloor n/3\rfloor-1$ on a path of diameter $D$ and set $D/\varepsilon$ large enough that the claimed bound is below $R=\lfloor \log_2 D/\log_2\log_2 D\rfloor$; if any honest party has not terminated by round $R$, the appendix's extension of RealAA is false. For the lower bound, take any deterministic $R$-round protocol with $R<\log_2 D/(\log_2\log_2 D+\log_2((n+t)/t))$ and inputs at the endpoints of a longest path; the constructed view chain must place two honest outputs more than distance one apart, so finding an execution where all honest outputs are within one would refute the lower bound.

Watch

Extended reading notes

Core claim

For any labeled tree $T$, the paper's central claim is that synchronous approximate agreement is solvable in $O(\log D(T)/\log\log D(T))$ rounds with optimal resilience $t<n/3$, and that no deterministic protocol can do better in general: every protocol needs $\Omega(\log D(T)/(\log\log D(T)+\log((n+t)/t)))$ rounds. Combining the two bounds makes the protocol optimal whenever $t\in\Theta(n)$. The lower bound adapts the real-valued view-chain argument of [19] to tree metrics by taking inputs from the endpoints of a longest path, so the same impossibility extends to every graph with diameter $D$. The upper bound improves the previous $O(\log D(T))$ bound of [35]. The same path-construction machinery, read through the clique tree of a block graph, yields approximate agreement protocols for block graphs with optimal resilience in the synchronous and asynchronous settings and optimal round complexity in the synchronous setting.

Load-bearing premise

The proof assumes the gradecast-based real-valued protocol RealAA, as extended in the appendix, really terminates in $O(\log(D/\varepsilon)/\log\log(D/\varepsilon))$ rounds for every $\varepsilon>0$; the tree protocol inherits that exact round count, so if this black-box guarantee fails the claimed upper bound collapses even though the reduction itself remains valid.

Editorial extensions

If this is right

  • Tree-valued approximate agreement now costs $O(\log D/\log\log D)$ rounds, replacing the previous $O(\log D)$ protocol of [35] and improving on the $O(\log|V|/\log\log|V|)$ intermediate protocol.
  • The protocol is asymptotically optimal in the standard constant-fraction Byzantine regime $t=\Theta(n)$; no deterministic protocol can shave the $\log\log$ factor in that regime.
  • Without cryptography the optimal resilience remains $t<n/3$, while with a public-key infrastructure and signatures the same round bound holds for every constant $c<1/2$, meaning $t=c n$.
  • Because the lower bound uses only a longest path inside the input space, the same impossibility applies to any graph, not just trees.
  • Block graphs inherit the round-optimal synchronous protocol and additionally obtain optimal-resilience protocols in the asynchronous model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the reduction is the bottleneck, any future improvement in round-optimal real-valued approximate agreement automatically improves tree-valued agreement, so the tree problem is asymptotically no harder than the real-line problem once a constant-round prefix finder exists.
  • The prefix-finder idea avoids full Byzantine agreement and may generalize to other convexity spaces admitting common-prefix paths, such as median graphs or other tree-decomposable spaces; testing the same graded-broadcast prefix construction on chordal graphs could show whether the open chordal-graph case can also be closed.
  • One practical extension is to measure convergence in terms of input spread rather than full diameter; the same reduction likely gives $O(\log(D/\varepsilon)/\log\log(D/\varepsilon))$ rounds for arbitrary target closeness $\varepsilon$, although the paper states only the $1$-close version.
  • The lower bound's dependence on $\log((n+t)/t)$ suggests the problem becomes harder as the corruption fraction grows; quantifying the regime where the $\log\log D$ term dominates could indicate where faster special-purpose protocols exist for very small $t$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The manuscript studies synchronous Byzantine approximate agreement (AA) on tree-shaped input spaces. Its main claims are a lower bound of Ω(log D(T) / (log log D(T) + log((n+t)/t))) rounds, adapted from Fekete's real-valued lower bound, and a matching upper-bound protocol with O(log D(T) / log log D(T)) rounds for t < n/3, extended to t < c n with c < 1/2 under PKI/signature assumptions. The upper bound is obtained by reducing tree AA to real-valued AA: a graded-broadcast primitive provides honest parties with prefix-comparable paths intersecting the honest inputs' convex hull, after which projections onto those paths and a real-valued AA protocol yield the final close, valid vertices. The title and abstract additionally promise results for block graphs and for general graphs, but the body does not contain such results.

Significance. If the lower-bound proof is repaired, the paper settles the asymptotic round complexity of synchronous AA on trees for t in Θ(n), closing a natural gap left by the O(log D) protocol of Nowak and Rybicki. The reduction framework is clean and modular: it isolates the tree-specific part in a graded-broadcast precomputation and reuses known real-valued AA protocols as black boxes. The appendices go some way toward making those black boxes self-contained, in particular extending the analysis of [6] to arbitrary ε > 0 and treating the t < n/2 authenticated case. The main weaknesses are a concrete gap in the stated Fekete inequality used for the lower bound, a garbled algebraic derivation in Theorem 2, and a major mismatch between the title/abstract and the actual content regarding block graphs and general graphs.

major comments (3)
  1. [Section 3, Eq. (1)] The displayed inequality K(R,D) ≥ D · sup{t_1···t_R : t_1,...,t_R ∈ N, t_1+...+t_R ≤ t}/(n+t)^R ≥ D·t^R/(R^R·(n+t)^R) is false under the stated integer domain. For example, with t=1 and R=2, every admissible integer tuple has a zero entry, so the supremum is 0, not 1/4. This is load-bearing because Theorem 2 uses exactly the second inequality to derive the contradiction D·t^R/(R^R·(n+t)^R) > 1, and the regime R > t is not excluded (e.g., t = Θ(1) with large D). Please either state Fekete's theorem with the correct quantifier, if the inequality is intended over nonnegative reals or under an additional R ≤ t restriction, or supply a separate argument covering the R > t case.
  2. [Section 3, Theorem 2 proof] The derivation in the proof of Theorem 2 does not hold as written. From the assumed bound R ≤ log_2 D / (log_2 log_2 D + log_2 δ), the correct implication is D^{1/R} ≥ δ·log_2 D, not D^{1/R} ≥ δ^{log_2 D}. The subsequent displayed computation, D^{1/R}/R ≥ δ^{log_2 D} · (log_2 log_2 Dδ)/log_2 D = δ^{log_2 log_2 Dδ}, is also not a valid algebraic consequence. The argument can be repaired: with A = log_2 D and δ = (n+t)/t, the bound on R gives D^{1/R}/R ≥ δ(log_2 A + log_2 δ) > δ for D ≥ 4. Please rewrite this part cleanly, since it is the step where asymptotic optimality is established.
  3. [Title and Abstract] The title and abstract promise approximate agreement on block graphs, including protocols with optimal resilience in both synchronous and asynchronous models and optimal round complexity in the synchronous model, and the abstract also claims lower bounds for any graph G. None of these statements appears in the body: there is no definition of block graphs, no block-graph protocol, and no graph lower bound beyond trees; Section 8 explicitly says it remains open whether similar round-optimal guarantees hold for broader classes of graphs. This is a serious scope mismatch. The authors must either add the promised block-graph and general-graph material or revise the title and abstract so that they accurately describe the tree results only.
minor comments (4)
  1. [Appendix B, Theorem 3] The stated bound R_RealAA(D, ε) < 7·log_2(D/ε)/log_2 log_2(D/ε) + 3 is undefined when D/ε ≤ e, since the denominator is non-positive in that range. In the tree protocol ε = 1 and D(T) can be a small constant, so the theorem statement should either assume D/ε is sufficiently large or include an explicit constant-round base case for D/ε = O(1).
  2. [Section 3, Theorem 2 proof] The notation R ≤ log_2 D / (log_2 log_2 D δ) is ambiguous and should be written with parentheses as R ≤ log_2 D / (log_2 log_2 D + log_2 δ). This would also prevent the garbled exponent manipulation that currently obscures the proof.
  3. [Appendix C, Theorem 9] The round-complexity expression in Theorem 9 has a denominator that can be non-positive for the stated range c ∈ [1/3, 1/2); the proof correctly says that the protocol of [24] is used in that case, but the formal statement should state this case split explicitly rather than leaving it to the surrounding discussion.
  4. [Section 6.1, Lemma 10] In the proof of Property 2, the statement that p' receives 'up to t < n−t messages supporting any path prefix different from P' relies on the fact that only Byzantine senders can appear with different content or different positive grades at different honest parties; it would improve clarity to spell this out, since grade-0 messages at one party can become grade-1 messages with different content at another party.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the upper bound is a black-box reduction to GC and real-valued AA, and the lower bound imports an external Fekete bound.

full rationale

The derivation chain is self-contained with respect to circularity. The upper bound reduces tree AA to two independent black boxes: the graded-broadcast protocol GC (Theorem 5, from Ben-Or-Dolev-Hoch [7]) and real-valued AA (Theorem 3, whose proof extends [6]/[7] claims to arbitrary epsilon in Appendix B). The tree-specific contribution, including Lemma 5's path-prefix conditions, OPT-PathsFinder, and the projection argument, is proved from GC properties and tree geometry rather than from the AA guarantee being established. The lower bound imports Fekete's R-round convergence bound (Theorem 1 of [19]) and derives a round lower bound from the requirement that, under 1-Agreement, K(R,D) is at most 1; this is an external theorem, and the contradiction argument is not definitionally tied to the upper-bound protocol. Self-citations are either provenance ([21]) or peer-reviewed external building blocks ([23], [24], [26], [35]) whose assumptions do not include the tree result, so they do not smuggle the conclusion into the premises. The integer-supremum inequality flagged by the skeptic in Theorem 1 is a potential correctness gap in the quoted lower bound when R exceeds t, but it is not a circularity: no displayed equation reduces to its own input by construction. Therefore no circular step is established.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fit to data; the paper introduces no new physical or mathematical entities. It relies on four external building blocks: Fekete's lower bound, two real-valued AA protocols, and gradecast. These are all published results, though several are co-authored by the present authors.

assumptions (4)
  • domain assumption Fekete's lower bound (Theorem 1 of [19]) for real-valued AA, adapted to trees.
    Used in Section 3 to prove the tree lower bound (Corollary 1 and Theorem 2); the adaptation is sketched, not fully proved.
  • domain assumption RealAA protocol of [6,7] with the extended round bound for arbitrary epsilon (Theorem 3).
    Used as the real-valued AA building block in the tree protocols; round bound proved in Appendix B from claims in [7].
  • domain assumption GC (gradecast) protocol of [6,7] with 3-round complexity for t<n/3, and PKI-based GC of [34] for t<n/2.
    OPT-PathsFinder relies on GC properties (Definition 4, Theorem 5, Theorem 7) to construct the common prefix paths.
  • domain assumption RealAA PKI combining Proxcensus [23] and the O(log(D/epsilon)) protocol of [24] (Theorem 8).
    Used for the authenticated t<n/2 result in Corollary 4; the combination is described in Appendix C.

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}
}
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 the authors.

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: • Termination:… view at source ↗
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 lower labe… view at source ↗
Figure 3
Figure 3. An input space tree [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (3 more)
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]
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 …
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 …

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. General Convex Agreement with Near-Optimal Communication

    cs.DC 2026-02 reject novelty 7.0 of 10

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

Reference graph

Works this paper leans on

45 extracted references · 7 canonical work pages · cited by 1 Pith paper

  1. [23]

    Round-optimal byzantine agreement

    Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang. Round-optimal byzantine agreement. In Orr Dunkelman and Stefan Dziembowski, editors,Advances in Cryptology – EUROCRYPT 2022, pages 96–119, Cham, 2022. Springer International Publishing. 23

    2022

  2. [6]

    Michael Ben-Or, Danny Dolev, and Ezra N. Hoch. Brief announcement: Simple gradecast based algorithms. In Nancy A. Lynch and Alexander A. Shvartsman, editors,Distributed Computing, pages 194–197, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

    2010

  3. [1]

    Optimal resilience asynchronous approxi- mate agreement

    Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approxi- mate agreement. In Teruo Higashino, editor,Principles of Distributed Systems, pages 229–239, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

    2005

  4. [2]

    The topology of look-compute-move robot wait-free algorithms with hard termination.Distributed Computing, 32(3):235–255, 2019.doi:10.1007/s00446-018-0345-3

    Manuel Alc´ antara, Armando Casta˜ neda, David Flores-Pe˜ naloza, and Sergio Rajsbaum. The topology of look-compute-move robot wait-free algorithms with hard termination.Distributed Computing, 32(3):235–255, 2019.doi:10.1007/s00446-018-0345-3

    doi:10.1007/s00446-018-0345-3 2019

  5. [3]

    Wait-free approximate agreement on graphs

    Dan Alistarh, Faith Ellen, and Joel Rybicki. Wait-free approximate agreement on graphs. In Tomasz Jurdzi´ nski and Stefan Schmid, editors,Structural Information and Communication Complexity, pages 87–105, Cham, 2021. Springer International Publishing.doi:10.1007/ 978-3-030-79527-6_6

    2021

  6. [4]

    The Step Complexity of Multidimensional Approximate Agree- ment

    Hagit Attiya and Faith Ellen. The Step Complexity of Multidimensional Approximate Agree- ment. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivi` ere, editors,26th International Con- ference on Principles of Distributed Systems (OPODIS 2022), volume 253 ofLeibniz Interna- tional Proceedings in Informatics (LIPIcs), pages 6:1–6:12, Dagstuhl, Germany, 20...

    doi:10.4230/lipics.opodis.2022.6 2022

  7. [5]

    Bandarupalli, A

    A. Bandarupalli, A. Bhat, S. Bagchi, A. Kate, C.-D. Liu-Zhang, and M. K. Reiter. Del- phi: Efficient asynchronous approximate agreement for distributed oracles. InProceedings of the 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 456–469, Brisbane, Australia, 2024. IEEE.doi:10.1109/DSN58291. 2024.00051

    work page arXiv 2024

  8. [7]

    Michael Ben-Or, Danny Dolev, and Ezra N. Hoch. Simple gradecast based algorithms.CoRR, abs/1007.1049, 2010. URL:http://arxiv.org/abs/1007.1049,arXiv:1007.1049

    arXiv 2010

Show all 45 references
  1. [8]

    Bender and Mart ´ ın Farach-Colton

    Michael A. Bender and Mart ´ ın Farach-Colton. The lca problem revisited. In Gaston H. Gonnet and Alfredo Viola, editors,LATIN 2000: Theoretical Informatics, pages 88–94, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg

    2000

  2. [9]

    Improved solutions for multidimensional approximate agreement via centroid computation.arXiv preprint arXiv:2306.12741, 2023

    Melanie Cambus and Darya Melnyk. Improved solutions for multidimensional approximate agreement via centroid computation.arXiv preprint arXiv:2306.12741, 2023. URL:https: //arxiv.org/pdf/2306.12741

    2023 arXiv

  3. [10]

    Con- vex Consensus with Asynchronous Fallback

    Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann. Con- vex Consensus with Asynchronous Fallback. In38th International Symposium on Distributed Computing (DISC), Madrid, Spain, October 2024

    2024

  4. [11]

    Gathering on rings under the look-compute-move model.Distributed Computing, 27(4):255–285, 2014.doi:10.1007/ s00446-014-0212-9

    Gianlorenzo D’Angelo, Gabriele Di Stefano, and Alfredo Navarra. Gathering on rings under the look-compute-move model.Distributed Computing, 27(4):255–285, 2014.doi:10.1007/ s00446-014-0212-9. 22

    2014

  5. [12]

    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.J. ACM, 33(3):499–516, May 1986. doi:10.1145/5925.5931

    1986

  6. [13]

    Raymond Strong

    Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983

    1983

  7. [14]

    Validated byzantine asynchronous multidi- mensional approximate agreement.arXiv preprint arXiv:2211.02126, 2022

    Maya Dotan, Gilad Stern, and Aviv Zohar. Validated byzantine asynchronous multidi- mensional approximate agreement.arXiv preprint arXiv:2211.02126, 2022. URL:https: //arxiv.org/abs/2211.02126,doi:10.48550/arXiv.2211.02126

    2022 doi arXiv

  8. [15]

    Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning)

    El-Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lˆ e-Nguyˆ en Hoang, and S´ ebastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning). InProceedings of the 35th International...

    2021

  9. [16]

    Genuinely distributed byzantine machine learning

    El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, Lˆ e Nguyˆ en Hoang, and S´ ebastien Rouault. Genuinely distributed byzantine machine learning. InProceedings of the 39th Sym- posium on Principles of Distributed Computing, PODC ’20, page 355–364, New York, NY, USA, 2020....

    2020

  10. [17]

    Asynchronous approximate agreement with quadratic communication, 2024

    Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous approximate agreement with quadratic communication, 2024. URL:https://arxiv.org/abs/2408.05495,arXiv:2408. 05495

    2024 arXiv

  11. [18]

    A. D. Fekete. Asynchronous approximate agreement. InProceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC ’87, page 64–76, New York, NY, USA, 1987. Association for Computing Machinery.doi:10.1145/41840.41846

    1987

  12. [19]

    Asymptotically optimal algorithms for approximate agreement.Distributed Computing, 4(1):9–29, 1990

    Alan David Fekete. Asymptotically optimal algorithms for approximate agreement.Distributed Computing, 4(1):9–29, 1990

    1990

  13. [20]

    Gathering asyn- chronous oblivious agents with local vision in regular bipartite graphs.Theoretical Computer Science, 509:26–41, 2013.doi:10.1016/j.tcs.2012.07.004

    Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Gathering asyn- chronous oblivious agents with local vision in regular bipartite graphs.Theoretical Computer Science, 509:26–41, 2013.doi:10.1016/j.tcs.2012.07.004

    2013 doi

  14. [21]

    Brief announcement: Towards round- optimal approximate agreement on trees

    Marc Fuchs, Diana Ghinea, and Zahra Parsaeian. Brief announcement: Towards round- optimal approximate agreement on trees. InProceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 54–57, New York, NY, USA, 2025. Association for Computing Machine...

    2025

  15. [22]

    Fast Multidimensional Asymptotic and Approximate Consensus

    Matthias F¨ ugger and Thomas Nowak. Fast Multidimensional Asymptotic and Approximate Consensus. In Ulrich Schmid and Josef Widder, editors,32nd International Symposium on Distributed Computing (DISC 2018), volume 121 ofLeibniz International Proceedings in In- formatics (LIPIcs...

    2018 doi

  16. [25]

    Multidimensional approximate agreement with asynchronous fallback

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. InProceedings of the 35th ACM Symposium on Paral- lelism in Algorithms and Architectures, SPAA ’23, page 141–151, New York, NY, USA, 2023. Association for...

    2023

  17. [26]

    Brief announcement: Communication-optimal convex agreement

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Brief announcement: Communication-optimal convex agreement. InProceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, page 492–495, New York, NY, USA, 2024. Association for Computing Machin...

    2024

  18. [27]

    Communication-Optimal Convex Agreement

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Communication-Optimal Convex Agreement. InThe 44th ACM Symposium on Principles of Distributed Computing (PODC), Huatulco, Mexico, June 2025

    2025

  19. [28]

    Brief announcement: Variants of approximate agreement on graphs and simplicial complexes

    J´ er´ emy Ledent. Brief announcement: Variants of approximate agreement on graphs and simplicial complexes. InProceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 427–430, New York, NY, USA, 2021. Association for Computing Machinery.doi:...

    2021

  20. [29]

    Optimal clock synchronization with signatures

    Christoph Lenzen and Julian Loss. Optimal clock synchronization with signatures. InPro- ceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 440–449, New York, NY, USA, 2022. Association for Computing Machinery.doi: 10.1145/3519270.3538444

    2022

  21. [30]

    The Impossibility of Approximate Agreement on a Larger Class of Graphs

    Shihao Liu. The Impossibility of Approximate Agreement on a Larger Class of Graphs. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivi` ere, editors,26th International Con- ference on Principles of Distributed Systems (OPODIS 2022), volume 253 ofLeibniz Inter- national Proce...

    2022 doi

  22. [31]

    Byzantine agreement with interval validity

    Darya Melnyk and Roger Wattenhofer. Byzantine agreement with interval validity. In2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS), pages 251–260, Salvador, Brazil, 2018. IEEE Computer Society.doi:10.1109/SRDS.2018.00036

    2018

  23. [32]

    Multidimensional approximate agreement in byzan- tine asynchronous systems

    Hammurabi Mendes and Maurice Herlihy. Multidimensional approximate agreement in byzan- tine asynchronous systems. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, ed- itors,45th ACM STOC, pages 391–400, Palo Alto, CA, USA, June 2013. ACM Press. doi:10.1145/2488608.2488657

    2013

  24. [33]

    Multidimensional agreement in byzantine systems.Distributed Computing, 28(6):423–441, 2015

    Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K Garg. Multidimensional agreement in byzantine systems.Distributed Computing, 28(6):423–441, 2015

    2015

  25. [34]

    Optimal and player-replaceable consensus with an honest majority

    Silvio Micali and Vinod Vaikuntanathan. Optimal and player-replaceable consensus with an honest majority. 2017. 24

    2017

  26. [35]

    Byzantine Approximate Agreement on Graphs

    Thomas Nowak and Joel Rybicki. Byzantine Approximate Agreement on Graphs. In Jukka Suomela, editor,33rd International Symposium on Distributed Computing (DISC 2019), vol- ume 146 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, ...

    2019 doi

  27. [36]

    Distributed computing with mobile robots: An introductory survey

    Maria Potop-Butucaru, Michel Raynal, and Sebastien Tixeuil. Distributed computing with mobile robots: An introductory survey. InProceedings of the 2011 14th International Con- ference on Network-Based Information Systems, NBIS ’11, page 318–324, USA, 2011. IEEE Computer Societ...

    2011 doi

  28. [37]

    Byzantine Agreement with Median Validity

    David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In Em- manuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru, editors,19th Interna- tional Conference on Principles of Distributed Systems (OPODIS 2015), volume 46 ofLeib- niz International Pr...

    2015 doi

  29. [38]

    Lili Su and Nitin H. Vaidya. Fault-tolerant multi-agent optimization: Optimal iterative dis- tributed algorithms. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, page 425–434, New York, NY, USA, 2016. Association for Computing Machiner...

    2016

  30. [39]

    Vaidya and Vijay K

    Nitin H. Vaidya and Vijay K. Garg. Byzantine vector consensus in complete graphs. In Panagiota Fatourou and Gadi Taubenfeld, editors,32nd ACM PODC, pages 65–73, Montreal, QC, July 2013. ACM.doi:10.1145/2484239.2484256

    2013

  31. [40]

    Brief announcement: Relaxed byzantine vector consensus

    Zhuolun Xiang and Nitin H Vaidya. Brief announcement: Relaxed byzantine vector consensus. InProceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 401–403, 2016

    2016

  32. [41]

    Zhuolun Xiang and Nitin H. Vaidya. Relaxed Byzantine Vector Consensus. In Panagiota Fatourou, Ernesto Jim´ enez, and Fernando Pedone, editors,20th International Conference on Principles of Distributed Systems (OPODIS 2016), volume 70 ofLeibniz International Proceed- ings in In...

    2016 doi

  33. [42]

    In the protocol of [23], the parties firstexpandtheir inputs from{0,1}to{0, ℓ}: input 0 remains 0, and input 1 becomesℓ. Afterwards, the parties run a series of iterations where they compute new values with the guarantee that (i) honest parties’ new values are in the range of ...

  34. [43]

    If V(T) >1, then for anyi < L , the verticesL i andL i+1 are adjacent inT

  35. [44]

    The listLcontains L ≤2· V(T) elements, and, for every vertexv∈V(T), we have L(v)̸=∅

  36. [45]

    Then, a vertexu is in the subtree rooted atvif and only ifL(u)⊆[i min, imax]

    Consider a vertexv∈V(T), and leti min = minL(v)andi max = maxL(v). Then, a vertexu is in the subtree rooted atvif and only ifL(u)⊆[i min, imax]

  37. [46]

    Proof.First, we prove thatListConstruction(T, v root) terminates in a finite amount of time

    For any two verticesv, v′ ∈V(T)and anyi∈L(v)andi ′ ∈L(v ′), the lowest common ancestor ofvandv ′ is in the set{L k : min(i, i′)≤k≤max(i, i ′)}. Proof.First, we prove thatListConstruction(T, v root) terminates in a finite amount of time. The algorithm follows a depth-first sear...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.