Pith. sign in

REVIEW 3 major objections 4 minor 65 references

Deterministic synchronous protocols bring Convex Agreement to near-optimal communication—O(L n log n) on finite spaces, O(L n^{1+o(1)}) on R^d—using extractor-built committees, with optimal rounds and near-optimal resilience.

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 ↗

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

T0 review reviewed 2026-08-02 challenge →

load-bearing objection The extractor-based committee idea is fresh and the target problem is right, but the main proof has a load-bearing gap: committee BA correctness is argued for real parties, not virtual parties, and D-fold replication can push the virtual byzantine fraction above the resilience threshold. the 3 major comments →

arxiv 2602.21411 v2 pith:MVCGY265 submitted 2026-02-24 cs.DC

General Convex Agreement with Near-Optimal Communication

Marc Dufay , Diana Ghinea , Anton Paramonov This is my paper
classification cs.DC MSC 68M1468Q25
keywords Convex AgreementByzantine Agreementcommunication complexityextractor graphssynchronous protocolsHelly numberadaptive adversarycommittee selection
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

This paper attempts to close most of the communication gap between Byzantine Agreement and its geometrically stricter relative, Convex Agreement, in which the agreed output must lie inside the convex hull of honest inputs. The authors construct deterministic synchronous protocols that, for long messages, use only O(L·n log n) bits on finite convexity spaces and O(L·n^{1+o(1)}) bits on Euclidean spaces—versus the Θ(L·n²) cost of broadcast-based approaches—while keeping optimal O(n) rounds and near-optimal resilience. The high-level idea is to compress the system rather than the values: an explicit extractor graph deterministically assigns parties to supernodes and supernodes to committees so that, even against an adaptive adversary, almost all committees keep an honest majority; iterating this compaction leaves a few supernodes holding valid values, which are then merged by a safe-area rule. If correct, this gives a general deterministic near-optimal communication solution for aggregation-style consensus on any convexity space with constant Helly number and finite dilation.

Core claim

The paper's central claim is that Convex Agreement on any convexity space with constant Helly number ω and finite dilation factor can be solved deterministically in the synchronous model with near-optimal communication: O(L n log n + n² κ log n) for finite spaces and O(L n^{1+o(1)} + n² log^{1+o(1)} n ·κ) for R^d, whenever honest inputs fit in L bits with L=Ω(n·κ). The protocol achieves O(n) rounds and, when L is known up front, resilience t<n/(ω+ε) (or t<n/(ω+ε+1) when L is unknown). The mechanism is iterative aggregation: start with n singleton supernodes; repeatedly pack them into constantly many committees chosen by an explicit extractor, have each committee compute a common value via a

What carries the argument

The load-bearing mechanism is a deterministic extractor-based committee assignment (Theorems 11, 12, 16): a bipartite expander graph built from an explicit high-min-entropy extractor assigns each party or supernode to constantly many groups so that any adversary controlling t parties can turn only a µ-fraction of committees 'bad'. Around this, the protocol wraps three components: supernodes—groups of parties that act as single entities; a supersending primitive that lets a group send an L-bit value to another group at cost O(L·(n_A+n_B)+κ n_B log n_B (n_A+n_B)) using RS shares, Merkle trees, and an inner BA; and a safe-area rule—the intersection of convex hulls of large sub-multisets—that co

Load-bearing premise

The proof's induction assumes that each committee the extractor marks as good contains few enough byzantine virtual parties for the inner Byzantine-Agreement call to solve agreement, but because a real party is replicated across constantly many supernodes and committees, the byzantine virtual-party fraction inside a committee can be several times larger than the byzantine real-party fraction, and the paper only bounds the latter, never proving the former stays below the BA pr

What would settle it

Take the construction with ω=2 and a small constant ε, enumerate the worst-case set of t=⌊n/(2+ε)⌋ byzantine real parties, and compute, for the extractor assignments of Theorems 11 and 12, the maximum byzantine virtual-party fraction over all committees. If any committee classified as 'good' has a virtual byzantine fraction reaching 1/2 (or 1/3 in the unauthenticated setting), the inner BA can fail there and the induction in Lemma 4 collapses; a direct simulation of the assignment for small n would settle the claim.

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

If this is right

  • For long messages (L=Ω(n·κ)), Convex Agreement on finite convexity spaces with constant Helly number runs in O(L n log n + n² κ log n) bits, replacing the Θ(L n²) of earlier broadcast-based protocols.
  • For Euclidean spaces R^d, the same framework runs in O(L n^{1+o(1)} + n² log^{1+o(1)} n · κ) bits with optimal O(n) rounds.
  • Parallel instances of Byzantine Agreement inherit the savings: q instances with total bit-length L can be solved with O(L n log n) communication and resilience t<n/(2+ε) (or t<n/(3+ε) unauthenticated).
  • The protocols are deterministic, work against adaptive corruptions, and achieve near-optimal resilience t<n/(ω+ε) when an input-length bound is known a priori.
  • When no bound on honest inputs' lengths is known, a length-estimation mechanism (with the same asymptotic communication, but resilience reduced by one, t<n/(ω+1+ε)) extends the result.

Where Pith is reading between the lines

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

  • The extractor-committee template may transfer to other validity conditions—median validity, k-th order validity, or external validity—wherever a deterministic safe-area rule exists; the same 'compress the system, not the values' principle could then give near-optimal communication for those tasks too.
  • Because each real party is replicated across several supernodes, the byzantine fraction of virtual parties inside a committee can differ from the byzantine fraction of real parties; proving that the virtual fraction stays below the inner BA's resilience threshold is a step the paper leaves implicit.
  • The known-length and unknown-length regimes differ by exactly one in the resilience denominator (ω+ε vs ω+1+ε), suggesting a possible inherent cost for not knowing L; whether that +1 can be removed is a natural stress test for the framework.
  • Since the committee assignment is an explicit constant-degree extractor, it is efficiently constructible; the same graph could be reused for other n-party tasks that need deterministic, load-balanced, adversarially resilient grouping.
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

3 major / 4 minor

Summary. The paper proposes deterministic synchronous Convex Agreement (CA) protocols for abstract convexity spaces, claiming near-optimal communication: O(L·n log n) for finite spaces with constant Helly number and dilation factor 1, and O(L·n^{1+o(1)}) for Euclidean spaces, with O(n) rounds and resilience t < n/(ω+ε). The approach is to compress the system rather than the values: extractor-based deterministic assignments arrange parties into supernodes and committees, committees run a CA subprotocol on their supernodes, and the number of supernodes is iteratively reduced. The paper also derives parallel-BA corollaries and an unknown-input-length variant.

Significance. If the main theorems were established, the paper would close the main gap between the Θ(L·n²) communication of prior general CA protocols and the Ω(L·n) lower bound, and the extractor-based deterministic committee construction would be a useful contribution to adaptive-adversary protocol design. The paper also gives a clear framework for abstract convexity spaces via Helly number and dilation factor. However, the proof of the central committee-correctness lemma contains a load-bearing gap: it does not establish that the internal Byzantine Agreement subprotocol runs within its resilience threshold on the relevant virtual parties. Because the main theorems depend on this lemma, the current manuscript does not support its central claims.

major comments (3)
  1. [§3.4, Lemma 4 proof] Lemma 4 applies Lemma 3 to a committee C_i by asserting that 'at most 1/(ω+ε/3) fraction of parties in C_i are byzantine.' Lemma 3's hypothesis, however, is that Π_BA achieves BA among the virtual parties in the committee. A real party can belong to up to D supernodes (Theorem 12), and those supernodes can be assigned to the same committee (Theorem 11), so a single byzantine real party can contribute up to D byzantine virtual parties. The good-committee definition bounds the real-party fraction, not the virtual-party fraction: Multi-Participation Safety only preserves correctness when the number of byzantine virtual parties is within the original BA threshold; it does not increase that threshold. The proof therefore never establishes that the BA subprotocol in a good committee meets its resilience bound. This invalidates Lemma 4 and the induction in Theorem 13.
  2. [§5, Theorem 11 and Theorem 12 composition] Even if the good-committee condition is read as a bound on virtual parties, the proof does not justify the claimed bound. Theorem 11 controls the number of committees with more than a 1/ω-fraction of bad supernodes; it does not control the per-committee fraction of byzantine supernodes. The proof's step 'there is at most a ((1/(ω+ε/3)−1/(ω+ε/2))/2)-fraction of them' treats a global bound on byzantine supernodes as if it applied within every good committee. A committee can have ≤ 1/ω bad supernodes while all of them are byzantine and of maximal size, making the byzantine virtual fraction exceed 1/(ω+ε/3). The global count of such committees is limited, but that limitation is not part of the argument. This is a second load-bearing gap in the proof that good committees are correct.
  3. [§3, definition of byzantine supernode] The threshold for a byzantine supernode is n_S · min(1/(ω+ε/2), ((1/(ω+ε/3)−1/(ω+ε/2))/2)). For small ε the second term is O(ε/ω²), far smaller than 1/(ω+ε/2). With t ≈ n/ω byzantine parties, each in D supernodes, the total number of byzantine memberships is Θ(Dn). The capacity of the allowed μN byzantine supernodes plus the byzantine memberships allowed in non-byzantine supernodes is O(μDn), which for small ε is o(Dn). Thus Theorem 12's promised bound on the number of byzantine supernodes cannot be satisfied for small ε. This appears to be a typographical error (likely max instead of min), but as written it is a direct contradiction and affects the main proof.
minor comments (4)
  1. [§3.4 and §3.1] The manuscript carefully distinguishes 'parties' from 'virtual parties' in §3.1, but the definition of a good committee in §3.4 and the proof of Lemma 4 use only 'parties.' This ambiguity is central to the soundness issue; the paper should explicitly define the good-committee condition on the virtual-party fraction and prove that condition from the extractor assignments.
  2. [§5, proof of Theorem 22] In the final inequality the proof writes |R| = ⌊n/s⌋, but the construction groups to exactly m right vertices, so |R| = m, which is not always equal to ⌊n/s⌋. The argument can be repaired by using s ≥ n/(2m), but as written the last step is incorrect.
  3. [§1 and §3.1] The resilience parameter ε is reused in Theorem 10 and in the main theorems. For ω=2 the target t < n/(2+ε) is below the authenticated-BA threshold only if the BA protocol's slack is chosen as a suitable function of ε; the paper should state this instantiation explicitly.
  4. [Throughout] There are several typos and informal citation issues, e.g., 'supersupernodes' in §5, and the abstract cites '[GL W, PODC’25]' informally instead of a numbered reference. These are minor and do not affect the substance.

Circularity Check

0 steps flagged

No significant circularity: the main claim is built from external extractor, BA, and safe-area lemmas; the self-citations are independent prior results and no parameter is fitted then reported as a prediction.

full rationale

Walking the derivation chain: the extractor committee theorems (Thm 11/12/16) are proved in §5 from Thm 21/22, which rest on external explicit-extractor and Ramanujan-graph constructions; these are not circular. The safe-area lemmas (Lemma 2/5) are quoted from [21, Lemma 15]; although [21] shares an author (Ghinea), the lemma is a general parameter-free statement about Helly numbers and does not assume the present paper's CA protocol or communication bounds, so under the reviewing rules it counts as independent support rather than load-bearing self-citation. The dilation-factor claims (Thms 4, 5) are proved from the definition of Helly number and a constructed extension encoding; no fitted parameter is renamed as a prediction. The BA and supersending primitives are black-boxed from [8], [54], [9], [39], [55], all external. The only notable issue is a correctness gap, not circularity: Lemma 4's proof concludes that 'BA solves Π_BA in C_i' from 'at most 1/(ω+ε/3) fraction of parties in C_i are byzantine', but this bounds real parties while BA runs over virtual parties; D-fold replication can inflate the byzantine virtual fraction. That is an unproven step, but it is not an equivalence-to-inputs-by-construction and does not make the central claim circular. Similarly, §D's statement that the safety properties 'apply naturally' is a missing proof, not a circular reduction. The central communication and resilience results are therefore not circular.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

The protocol introduces no new physical or computational entities. The 'supernode' is a grouping construct and 'dilation factor' is a property of the convexity space, both derived. The main external inputs are the BA protocols, the extractor construction, and the safe-area lemma. There are no fitted data parameters; all constants are set analytically.

axioms (4)
  • standard math Existence of explicit Ramanujan graphs for arbitrary n and degree D, constructible in polynomial time (Cohen 2016).
    Used in Theorem 21 to construct explicit extractors with the required parameters; if the cited construction does not cover the needed n/D regime, the committee assignment theorems fail. Appears in §5, Proof of Theorem 21.
  • domain assumption The BA protocols of [8] (unauthenticated) and [54] (authenticated) satisfy Multi-Participation Safety and Extra-Corruptions Safety.
    Lemmas 1–4 and all complexity bounds rely on these properties; the paper only sketches the argument in Appendix D and does not provide a complete proof for each cited protocol.
  • domain assumption Collision-resistant hash function, and in authenticated settings PKI plus secure signatures.
    Stated in §2 as the cryptographic basis; the proofs assume no collisions and no signature forgeries, so the guarantees are computational rather than unconditional.
  • standard math The safe-area lemma (Lemma 9 from [21]) is valid for the abstract convexity spaces considered.
    Lemmas 2 and 5 are direct consequences; any subtle assumption about the convexity space or the Helly number would propagate into the validity proofs. Cited from prior published work with some author overlap.

reviewed 2026-08-02 · how reviews work

0 comments
Cite this review

Pith. "Pith review of General Convex Agreement with Near-Optimal Communication." pith.science (2026). https://pith.science/paper/MVCGY265

@misc{pith2026260221411,
  author       = {Pith},
  title        = {Pith review of: General Convex Agreement with Near-Optimal Communication},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MVCGY265}},
  note         = {Machine review of arXiv:2602.21411}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Byzantine Agreement (BA) considers a setting of $n$ parties out of which up to $t$ can be byzantine (malicious), and requires the honest parties to agree on an input subject to a condition called \emph{validity}: if all honest parties have input $v$, the output agreed upon must be $v$. Convex Agreement (CA) strengthens BA by requiring the output agreed upon to lie in the convex hull of the honest parties' inputs. This validity condition captures aggregation tasks, such as robust learning and sensor fusion, where honest inputs may differ but should still constrain the final decision. Existing protocols for CA over general convexity spaces require at least $O(L \cdot n^2)$ bits of communication for $L$-bit inputs, leaving a gap with BA's $\Omega(L \cdot n)$ lower bound. We investigate this gap, and we present deterministic synchronous CA protocols with near-optimal communication complexity in the long-message regime. When $L=\Omega(n\cdot\kappa)$, where $\kappa$ is a security parameter, our protocols use $\mathcal{O}(L\cdot n\log n)$ bits of communication for finite convexity spaces and $\mathcal{O}(L\cdot n^{1+o(1)})$ communication for Euclidean spaces $\mathbb{R}^d$. Our protocols also have asymptotically optimal round complexity $\mathcal{O}(n)$. If an upper bound $L$ on the honest inputs' length in bits is known in advance, we achieve near-optimal resilience $t<n/(\omega+\varepsilon)$ for any constant $\varepsilon>0$, where $\omega$ is the Helly number of the convexity space. When no such bound is known, we achieve resilience $t<n/(\omega+\varepsilon+1)$. As a sample application, we show how our protocols can be used to obtain efficient solutions for parallel instances of BA. Our main technical contribution is the use of extractor graphs to obtain a deterministic assignment of parties to committees, which is robust against adaptive adversaries.

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

65 extracted references · 10 canonical work pages

  1. [1]

    Optimal resilience asynchronous approximate agreement

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

    2005

  2. [2]

    Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi

    Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Peter Robinson and Faith Ellen, editors,38th ACM PODC, pages 317–326. ACM, July / August 2019.doi:10.1145/3293611. 3331629

    work page doi:10.1145/3293611 2019

  3. [3]

    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

  4. [4]

    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 doi:10.1007/978-3-030-79527-6_ 2021

  5. [5]

    Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Chen-Da Liu-Zhang, and Michael K. Reiter. Delphi: Efficient asynchronous approximate agreement for distributed oracles. In2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 456–469, 2024.doi:10.1109/DSN58291.2024.00051

    arXiv 2024

  6. [6]

    Reiter, Aniket Kate, and Saurabh Bagchi

    Akhil Bandarupalli, Adithya Bhat, Somali Chaterji, Michael K. Reiter, Aniket Kate, and Saurabh Bagchi. Sensorbft: Fault-tolerant target localization using voronoi diagrams and approximate agree- ment. In2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS), pages 186–197, 2024.doi:10.1109/ICDCS60910.2024.00026

    Pith/arXiv arXiv 2024

  7. [7]

    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

  8. [8]

    Garay, and Kenneth J

    Piotr Berman, Juan A. Garay, and Kenneth J. Perry.Bit Optimal Distributed Consensus, pages 313–321. Springer US, Boston, MA, 1992.doi:10.1007/978-1-4615-3422-8_27

    work page doi:10.1007/978-1-4615-3422-8_27 1992

  9. [9]

    Efficient adaptively-secure byzantine agreement for long messages

    Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, and Kartik Nayak. Efficient adaptively-secure byzantine agreement for long messages. In Shweta Agrawal and Dongdai Lin, editors,ASI- ACRYPT 2022, Part I, volume 13791 ofLNCS, pages 504–525. Springer, Cham, December 2022. doi:10.1007/978-3-031-22963-3_17

    work page doi:10.1007/978-3-031-22963-3_17 2022

  10. [10]

    Asynchronous byzantine agreement with subquadratic communication

    Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 ofLNCS, pages 353–380. Springer, Cham, November 2020. doi:10.1007/978-3-030-64375-1_13

    work page doi:10.1007/978-3-030-64375-1_13 2020

  11. [11]

    Asynchronous verifiable information dispersal

    Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In24th IEEE Symposium on Reliable Distributed Systems (SRDS’05), pages 191–201, Orlando, FL, USA, 2005. IEEE, IEEE Computer Society.doi:10.1109/RELDIS.2005.9

    doi:10.1109/reldis.2005.9 2005

  12. [12]

    Approximate Agreement Algorithms for Byzantine Collaborative Learning

    M´ elanie Cambus, Darya Melnyk, Tijana Milentijevi´ c, and Stefan Schmid. Approximate Agreement Algorithms for Byzantine Collaborative Learning. InProceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 89–100, New York, NY, USA, 2025. Association for Computing Machinery.doi:10.1145/3694906.3743343. 23

    arXiv 2025

  13. [13]

    Information-theoretic broadcast with dishon- est majority for long messages

    Wutichai Chongchitmate and Rafail Ostrovsky. Information-theoretic broadcast with dishon- est majority for long messages. In Amos Beimel and Stefan Dziembowski, editors,TCC 2018, Part I, volume 11239 ofLNCS, pages 370–388. Springer, Cham, November 2018.doi:10.1007/ 978-3-030-03807-6_14

    2018

  14. [14]

    DARE to agree: Byzantine agreement with optimal resilience and adaptive communication

    Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. DARE to agree: Byzantine agreement with optimal resilience and adaptive communication. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors,43rd ACM PODC, pages 145–156. ACM, June 2024.doi:10.1145/3662158.3662792

    arXiv 2024

  15. [16]

    Modular construction of a byzantine agreement protocol with optimal message bit complexity.Information and Computation, 97(1):61–85, 1992

    Brian A Coan and Jennifer L Welch. Modular construction of a byzantine agreement protocol with optimal message bit complexity.Information and Computation, 97(1):61–85, 1992

    1992

  16. [17]

    Michael B. Cohen. Ramanujan graphs in polynomial time. In Irit Dinur, editor,57th FOCS, pages 276–281. IEEE Computer Society Press, October 2016.doi:10.1109/FOCS.2016.37

    doi:10.1109/focs.2016.37 2016

  17. [18]

    Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp

    Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In34th International Symposium on Distributed Computing, 2020

    2020

  18. [19]

    Brief Announce- ment: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communica- tion

    Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announce- ment: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communica- tion. In39th International Symposium on Distributed Computing (DISC 2025), volume 356, pages 52:1–52:8, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. ...

    work page doi:10.4230/lipics.disc.2025.52 2025

  19. [20]

    A Fair and Resilient Decentralized Clock Network for Transaction Ordering

    Andrei Constantinescu, Diana Ghinea, Lioba Heimbach, Zilin Wang, and Roger Wattenhofer. A Fair and Resilient Decentralized Clock Network for Transaction Ordering. In Alysson Bessani, Xavier D´ efago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi, editors,27th International Con- ference on Principles of Distributed Systems (OPODIS 2023), volume 286 ofLe...

    2023

  20. [21]

    Convex Consensus with Asynchronous Fallback

    Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann. Convex Consensus with Asynchronous Fallback. In38th International Symposium on Distributed Com- puting (DISC 2024), volume 319 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Infor-...

    doi:10.4230/lipics.disc.2024.15 2024

  21. [22]

    ” helly’s theorem and its relatives,” in convexity

    Ludwig Danzer. ” helly’s theorem and its relatives,” in convexity. InProc. Symp. Pure Math., volume 7, pages 101–180. Amer. Math. Soc., 1963

    1963

  22. [23]

    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

    arXiv 1986

  23. [24]

    Bounds on information exchange for byzantine agreement

    Danny Dolev and R¨ udiger Reischuk. Bounds on information exchange for byzantine agreement. In Robert L. Probert, Michael J. Fischer, and Nicola Santoro, editors,1st ACM PODC, pages 132–140. ACM, August 1982.doi:10.1145/800220.806690. 24

    arXiv 1982

  24. [25]

    Raymond Strong

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

    1983

  25. [26]

    Collaborative learning in the jungle (decentralized, byzantine, heteroge- neous, 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, heteroge- neous, asynchronous and nonconvex learning). InProceedings of the 35th International Conference on Neural Information Processing Systems, NIPS ’21, Red Hook, NY, ...

    2021

  26. [27]

    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 Sympo- sium on Principles of Distributed Computing, PODC ’20, page 355–364, New York, NY, USA, 2020. Association for Computing Machinery.doi:10.1145/3382734.3405695

    arXiv 2020

  27. [28]

    Asynchronous approximate agreement

    Alan David Fekete. Asynchronous approximate agreement. In Fred B. Schneider, editor,6th ACM PODC, pages 64–76. ACM, August 1987.doi:10.1145/41840.41846

    arXiv 1987

  28. [29]

    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

  29. [30]

    Impossibility of distributed consensus with one faulty process.Journal of the ACM (JACM), 32(2):374–382, 1985

    Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process.Journal of the ACM (JACM), 32(2):374–382, 1985

    1985

  30. [31]

    Optimally efficient multi-valued Byzantine agreement

    Matthias Fitzi and Martin Hirt. Optimally efficient multi-valued Byzantine agreement. In Eric Ruppert and Dahlia Malkhi, editors,25th ACM PODC, pages 163–168. ACM, July 2006.doi: 10.1145/1146381.1146407

    arXiv 2006

  31. [32]

    Multidimensional byzantine agreement in a synchronous setting.Applicable Algebra in Engineering, Communication and Computing, 35:1–19, 03 2022.doi:10.1007/s00200-022-00548-5

    Andrea Flamini, Riccardo Longo, and Alessio Meneghetti. Multidimensional byzantine agreement in a synchronous setting.Applicable Algebra in Engineering, Communication and Computing, 35:1–19, 03 2022.doi:10.1007/s00200-022-00548-5

    work page doi:10.1007/s00200-022-00548-5 2022

  32. [33]

    Round-optimal approximate agreement on trees,

    Marc Fuchs, Diana Ghinea, and Zahra Parsaeian. Round-optimal approximate agreement on trees,

  33. [34]

    Broadcast extensions with optimal communication and round complexity

    Chaya Ganesh and Arpita Patra. Broadcast extensions with optimal communication and round complexity. In George Giakkoupis, editor,35th ACM PODC, pages 371–380. ACM, July 2016. doi:10.1145/2933057.2933082

    arXiv 2016

  34. [35]

    Optimal load-balanced scalable distributed agreement

    Yuval Gelles and Ilan Komargodski. Optimal load-balanced scalable distributed agreement. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,56th ACM STOC, pages 411–422. ACM Press, June 2024.doi:10.1145/3618260.3649736

    arXiv 2024

  35. [36]

    SoK: Approximate Agreement

    Diana Ghinea and Chen-Da Liu-Zhang. SoK: Approximate Agreement. InFinancial Cryptography and Data Security 2026 (FC), St. Kitts, March 2026

    2026

  36. [38]

    Multidimensional approximate agree- ment with asynchronous fallback

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agree- ment with asynchronous fallback. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 141–151, New York, NY, USA, 2023. Association for Computing Machinery.doi:10.1145/3558481.3591105. 25

    arXiv 2023

  37. [39]

    Communication-optimal convex agree- ment

    Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Communication-optimal convex agree- ment. In Alkida Balliu and Fabian Kuhn, editors,44th ACM PODC, pages 39–49. ACM, June 2025. doi:10.1145/3732772.3733551

    arXiv 2025

  38. [40]

    Multi-valued byzantine broadcast: Thet < ncase

    Martin Hirt and Pavel Raykov. Multi-valued byzantine broadcast: Thet < ncase. In Palash Sarkar and Tetsu Iwata, editors,ASIACRYPT 2014, Part II, volume 8874 ofLNCS, pages 448–465. Springer, Berlin, Heidelberg, December 2014.doi:10.1007/978-3-662-45608-8_24

    work page doi:10.1007/978-3-662-45608-8_24 2014

  39. [41]

    Network extractor protocols

    Yael Tauman Kalai, Xin Li, Anup Rao, and David Zuckerman. Network extractor protocols. In49th FOCS, pages 654–663. IEEE Computer Society Press, October 2008.doi:10.1109/FOCS.2008.73

    work page doi:10.1109/focs.2008.73 2008

  40. [42]

    From almost everywhere to everywhere: Byzantine agreement with eO(n3/2) bits

    Valerie King and Jared Saia. From almost everywhere to everywhere: Byzantine agreement with eO(n3/2) bits. In Idit Keidar, editor,Distributed Computing, pages 464–478, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg

    2009

  41. [43]

    Breaking theO(n 2) bit barrier: scalable byzantine agreement with an adaptive adversary

    Valerie King and Jared Saia. Breaking theO(n 2) bit barrier: scalable byzantine agreement with an adaptive adversary. In Andr´ ea W. Richa and Rachid Guerraoui, editors,29th ACM PODC, pages 420–429. ACM, July 2010.doi:10.1145/1835698.1835798

    arXiv 2010

  42. [44]

    Scalable leader election

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In17th SODA, pages 990–999. ACM-SIAM, January 2006

    2006

  43. [45]

    The byzantine generals problem.ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982

    Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem.ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982

    1982

  44. [46]

    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. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors,40th ACM PODC, pages 427–430. ACM, July 2021.doi:10.1145/3465084.3467946

    arXiv 2021

  45. [47]

    Optimal clock synchronization with signatures

    Christoph Lenzen and Julian Loss. Optimal clock synchronization with signatures. In Alessia Milani and Philipp Woelfel, editors,41st ACM PODC, pages 440–449. ACM, July 2022.doi: 10.1145/3519270.3538444

    arXiv 2022

  46. [48]

    Guanfeng Liang and Nitin H. Vaidya. Error-free multi-valued consensus with byzantine failures. In Cyril Gavoille and Pierre Fraigniaud, editors,30th ACM PODC, pages 11–20. ACM, June 2011. doi:10.1145/1993806.1993809

    arXiv 2011

  47. [49]

    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

    arXiv 2018

  48. [50]

    Multidimensional approximate agreement in byzantine asynchronous systems

    Hammurabi Mendes and Maurice Herlihy. Multidimensional approximate agreement in byzantine asynchronous systems. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors,45th ACM STOC, pages 391–400. ACM Press, June 2013.doi:10.1145/2488608.2488657

    arXiv 2013

  49. [51]

    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

  50. [52]

    A digital signature based on a conventional encryption function

    Ralph C Merkle. A digital signature based on a conventional encryption function. InConference on the theory and application of cryptographic techniques, pages 369–378. Springer, 1987

    1987

  51. [53]

    Asynchronous Approximate Agreement with Quadratic Communication

    Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous Approximate Agreement with Quadratic Communication. In29th International Conference on Principles of Distributed Systems (OPODIS 2025), volume 361, pages 16:1–16:26, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi:10.4230/LIPIcs.OPODIS.2025.16. 26

    doi:10.4230/lipics.opodis.2025.16 2025

  52. [54]

    Optimal communication complexity of authenticated byzantine agree- ment

    Atsuki Momose and Ling Ren. Optimal communication complexity of authenticated byzantine agree- ment. In35th International Symposium on Distributed Computing (DISC 2021). Schloss Dagstuhl- Leibniz-Zentrum f¨ ur Informatik, 2021

    2021

  53. [55]

    Vaidya, and Zhuolun Xiang

    Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In Hagit Attiya, editor,34th International Symposium on Distributed Computing (DISC 2020), volume 179 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:17, Dagstuhl, Germany, 2020. Schloss Dag...

    work page doi:10.4230/lipics.disc.2020.28 2020

  54. [56]

    Accumulators from bilinear pairings and applications

    Lan Nguyen. Accumulators from bilinear pairings and applications. InTopics in Cryptology–CT- RSA 2005: The Cryptographers’ Track at the RSA Conference 2005, San Francisco, CA, USA, February 14-18, 2005. Proceedings, pages 275–292. Springer, 2005

    2005

  55. [57]

    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), volume 146 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Ger- many, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL:http://drops.dagstuh...

    doi:10.4230/lipics.disc.2019.29 2019

  56. [58]

    Reaching agreement in the presence of faults

    Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228–234, 1980

    1980

  57. [59]

    Polynomial codes over certain finite fields.Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960

    Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields.Journal of the society for industrial and applied mathematics, 8(2):300–304, 1960

    1960

  58. [60]

    Formalizing human ignorance

    Phillip Rogaway. Formalizing human ignorance. In Phong Q. Nguyen, editor,Progress in Cryptology - VIETCRYPT 2006, pages 211–228, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg

    2006

  59. [61]

    Ronen Shaltiel.Recent Developments in Explicit Constructions of Extractors, pages 189–228.doi: 10.1142/9789812562494_0013

    doi:10.1142/9789812562494_0013

  60. [62]

    Byzantine Agreement with Median Validity

    David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru, editors,19th International Conference on Principles of Distributed Systems (OPODIS 2015), volume 46 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 1–14, Dagstuhl, Germany, 2016. Schloss Dagstu...

    2015

  61. [63]

    Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms

    Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. InProceedings of the 2016 ACM symposium on principles of distributed computing, pages 425–434, 2016

    2016

  62. [64]

    Extending binary byzantine agreement to multivalued byzantine agreement.Information Processing Letters, 18(2):73–76, 1984

    Russell Turpin and Brian A Coan. Extending binary byzantine agreement to multivalued byzantine agreement.Information Processing Letters, 18(2):73–76, 1984

    1984

  63. [65]

    Salil P. Vadhan. Pseudorandomness.Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 12 2012.doi:10.1561/0400000010

    doi:10.1561/0400000010 2012

  64. [66]

    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. ACM, July 2013.doi: 10.1145/2484239.2484256. 27 Appendix A Dilation Factor ofR d We present the proof of Theorem 5, restated below. Theorem 5.Letd >0andCbe a convex subset ofR d with straight-line...

    arXiv 2013

  65. [2025]

    URL:https://arxiv.org/abs/2502.05591,arXiv:2502.05591

    Pith/arXiv arXiv

This paper was first reviewed by deepseek-v4-flash on August 2, 2026.