pith. sign in

arxiv: 2502.05591 · v4 · 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

Pith reviewed 2026-05-23 04:01 UTC · model grok-4.3

classification 💻 cs.DC
keywords approximate agreementByzantine faultstreesblock graphsround complexityresiliencesynchronous protocolsdistributed computing
0
0 comments X

The pith

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

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

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.

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.

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.

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 ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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.

pith-pipeline@v0.9.0 · 5843 in / 1403 out tokens · 133888 ms · 2026-05-23T04:01:26.701207+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 1 internal anchor

  1. [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

    work page 2005

  2. [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

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

  3. [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

    work page 2021

  4. [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...

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

  5. [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 doi:10.1109/dsn58291 2024

  6. [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

    work page 2010

  7. [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

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  8. [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

    work page 2000

  9. [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

    work page arXiv 2023

  10. [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

    work page 2024

  11. [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

    work page 2014

  12. [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

    work page doi:10.1145/5925.5931 1986

  13. [13]

    Raymond Strong

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

    work page 1983

  14. [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

    work page doi:10.48550/arxiv.2211.02126 2022

  15. [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 Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, US...

    work page 2021

  16. [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. Association for Computing Machinery.doi:10.1145/3382734.3405695

    work page doi:10.1145/3382734.3405695 2020

  17. [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

    work page arXiv 2024

  18. [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

    work page doi:10.1145/41840.41846 1987

  19. [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

    work page 1990

  20. [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

    work page doi:10.1016/j.tcs.2012.07.004 2013

  21. [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 Machinery.doi:10.1145/3732772.3733555

    work page doi:10.1145/3732772.3733555 2025

  22. [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), pages 27:1–27:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz- Zentru...

    work page doi:10.4230/lipics.disc.2018.27 2018

  23. [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

    work page 2022

  24. [24]

    Optimal synchronous approx- imate agreement with asynchronous fallback

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Optimal synchronous approx- imate agreement with asynchronous fallback. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 70–80, New York, NY, USA, 2022. Association for Computing Machinery.doi:10.1145/3519270.3538442

    work page doi:10.1145/3519270.3538442 2022

  25. [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 Computing Machinery.doi:10.1145/3558481.3591105

    work page doi:10.1145/3558481.3591105 2023

  26. [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 Machinery.doi:10.1145/3662158.3662782

    work page doi:10.1145/3662158.3662782 2024

  27. [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

    work page 2025

  28. [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:10.1145/3465084.3467946

    work page doi:10.1145/3465084.3467946 2021

  29. [29]

    Optimal synchronous approx- imate agreement with asynchronous fallback

    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

    work page doi:10.1145/3519270.3538444 2022

  30. [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 Proceedings in Informatics (LIPIcs), pages 22:1–22:20, Dagstuhl, Germany, 2023. Schlo...

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

  31. [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

    work page doi:10.1109/srds.2018.00036 2018

  32. [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

    work page doi:10.1145/2488608.2488657 2013

  33. [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

    work page 2015

  34. [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

    work page 2017

  35. [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. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL:http: //drops.dagstu...

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

  36. [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 Society.doi:10.1109/NBiS.2011.55

    work page doi:10.1109/nbis.2011.55 2011

  37. [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 Proceedings in Informatics (LIPIcs), pages 1–14, Dagstuhl, Germany, 2016. Schloss ...

    work page doi:10.4230/lipics.opodis.2015.22 2015

  38. [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 Machinery.doi:10.1145/2933057.2933105

    work page doi:10.1145/2933057.2933105 2016

  39. [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

    work page doi:10.1145/2484239.2484256 2013

  40. [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

    work page 2016

  41. [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 Informatics (LIPIcs), pages 26:1–26:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl ...

    work page doi:10.4230/lipics.opodis.2016.26 2016

  42. [42]

    Hence, in both cases,closestInt(j ′)−closestInt(j)≤1

    This leads to a contradiction, as it impliesj ′ −j >1. Hence, in both cases,closestInt(j ′)−closestInt(j)≤1. BRealAAin thet < n/3setting As mentioned in Section 4, the analysis of [6] regardingRealAAproves thatAAis achieved for ε= 1/n. Theorem 3 extends the analysis for anyε >0. In order to prove Theorem 3, we make use of a few results in the full version...

    work page

  43. [43]

    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 the honest parties’ values at the beginning of the iteration, (ii) the range of ...

    work page

  44. [44]

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

    work page

  45. [45]

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

    work page

  46. [46]

    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]

    work page

  47. [47]

    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 search (dfs) traversal, which has a time complexity ofO(|V|+|E|) for a graph with v...

    work page