Pith. sign in

REVIEW 2 major objections 4 minor 39 references

Subcubic Coin Tossing in Asynchrony without PKI

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

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

Pith's one-line read This paper claims that any strong but costly asynchronous common coin can be transformed into a cheaper weak coin, yielding the first setup-free asynchronous coins with subcubic communication and constant fairness against Θ(n) adaptive byza

desk verdict Real advance in coin complexity, but the proof needs a concurrent-composition assumption it doesn't state. read the letter →

arxiv 2603.02071 v2 pith:VKVDVMPE submitted 2026-03-02 cs.DC cs.CR

Mose Mizrahi , Roger Wattenhofer This is my paper · ORCID
classification cs.DCcs.CR MSC 68W1568M14
keywords commoncoinbyzantineagreementasynchronousprotocolsadaptiveadversarycommittee-basedtransformationcommunicationcomplexityverifiablesecretsharingsetup-free
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

The paper is trying to establish that expensive, rarely failing 'strong' coins can be systematically converted into cheap, lower-fairness 'weak' coins, and that this conversion is enough to break the long-standing n^3 communication barrier for setup-free asynchronous coin tossing. The transformation is committee-based: it splits the parties into many small committees, runs the strong coin inside each committee, and lets the committees act as virtual parties in a virtual majority-based coin. The paper proves a general trade-off — a strong coin costing O~(n^k) bits yields a weak coin costing O~(ε^{-2k} n^{3-2/k}) bits while losing only εn fault tolerance — and instantiates it with a perfectly secure coin for t ≤ (1/4−ε)n faults at O~(n^{2.5}) bits, and a hash-based coin for t ≤ (1/3−ε)n faults at O~(n^{7/3}) bits. If correct, this gives the first setup-free asynchronous byzantine agreement protocols with subcubic communication against a linear number of adaptive byzantine faults.

What carries the argument

The central machinery is a committee-based transformation T(Cstr,z,k,ε,α) that simulates a q-party majority coin with committees as virtual parties. The three load-bearing components are: (1) Lemma 5.1, a probabilistic construction of deterministic committees that guarantees fewer than c bad committees for any set of at most (α−ε)n corrupted parties; (2) the Publish protocol, which lets a committee reveal its bit to nearly all parties in O(s^2 + n(s/d + log n)) messages by combining crusader agreement with a sparse bipartite graph whose right-hand vertices have Δ neighbors; (3) an anti-concentration bound on symmetric binomials (Lemma 5.2) that, together with the odd choice of q, keeps the m

What would settle it

Find one adaptive adversary that corrupts at most (α−ε)n parties and makes at least c = ⌈z'√q/3⌉ committees 'bad' (each containing at least αs corrupted members). Lemma 5.1 asserts this is impossible for the paper's deterministic committee list; if such a corruption set exists, the transformed coin's fairness collapses because the majority of committee bits is no longer guaranteed to be random.

Watch

Extended reading notes

Core claim

On its own terms, the paper's discovery is that a strong binary coin — one whose good event happens with probability δ very close to 1 — can be amplified down into a weak coin: choose q odd committees of size s, run one independent strong-coin instance inside each committee, publish each committee's bit via a deliberately imperfect publication protocol based on crusader agreement and sparse communication graphs, and have every party take the majority of the published committee bits. The committees are chosen deterministically so that, against any adaptive adversary corrupting at most (α−ε)n parties, fewer than O(√q) committees are 'bad'; the strong-coin failures plus the majority bias of an

Load-bearing premise

The whole construction stands or falls with the δ-fair strong coin: it must keep its δ ≈ 1−O(1/q) failure probability even when many instances run concurrently on overlapping committees under an adaptive adversary, and the concrete instantiations inherit the secrecy and security of their underlying verifiable-secret-sharing schemes.

Editorial extensions

If this is right

  • For any strong coin with cost M(n)=O(n^c), c>2, and O(log n) message size, the transformed weak coin costs O(n^{3-2/c} log n) messages of the same size — the trade-off improves as c shrinks toward 2.
  • With an O(1)-toss binary byzantine agreement protocol, these coins yield setup-free asynchronous byzantine agreement with o(n^3) communication against Θ(n) adaptive byzantine faults; the perfectly secure coin achieves even o(n^4) bits under the paper's accounting.
  • The same technique gives leader election and multi-bit outputs with only polylogarithmic overhead, either by parallel independent tosses or by batching the per-committee strong-coin and publication steps.
  • If the strong coin is only λ-live, the transformed coin is still 1−(1−λ)^q-live, so the method also converts probabilistic-liveness coins into coins with near-deterministic liveness.
  • The transformation reduces fault tolerance by exactly εn relative to the strong coin it consumes, giving protocol designers a direct knob for trading resilience for communication.

Reading between the lines

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

  • The virtual-party trick is not tied to binary outputs: the same committee-and-majority structure could, in principle, amplify strong coins with larger output domains, giving a more direct route to multivalued coins than the paper's parallel-bits approach.
  • The paper's O(log n) latency comes from the strong coins needing Θ(log n) rounds to reach failure probability 2^{-Θ(log n)}; a constant-latency strong coin with the same cost would immediately give a constant-latency weak coin under this same transformation.
  • Because the transformation treats the strong coin as a black box, improving the underlying strong coin's cost or security should automatically propagate through the same formula; this suggests the explicit open targets of O(n^2) communication and O(1) latency are exactly the places where such an improvement would show up.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies asynchronous common coin tossing among n parties with an adaptive byzantine adversary and no PKI/setup. Its main contribution is a committee-based transformation T(Cstr,z,k,ε,α) that takes a δ-fair "strong" binary common coin Cstr costing O~(n^k) communication and produces a weaker binary coin costing O~(ε^{-2k} n^{3-2/k}) communication, while sacrificing an εn fraction of fault tolerance and losing only an arbitrarily small constant of fairness. The construction fixes q deterministic committees, runs Cstr inside each committee, publishes the resulting bits through a sparse crusader-agreement-based Publish protocol, and then aggregates committee outputs in a virtual Ben-Or style majority. The paper instantiates the strong coin with AVSS-based protocols from prior work to obtain a perfectly secure coin Cperfect for t≤(1/4−ε)n with O~(n^{2.5}) communication, and a hash-based cryptographic coin Ccrypto for t≤(1/3−ε)n with O~(n^{7/3}) communication. If the proof were complete, these would be the first setup-free asynchronous common coins with o(n^3) communication against Θ(n) adaptive byzantine faults.

Significance. The claimed result is significant: breaking the O(n^3) communication barrier for setup-free, PKI-free asynchronous common coins against Θ(n) adaptive faults would be a meaningful step, and the paper gives explicit complexity tradeoffs as well as concrete instantiations. The committee-based transformation is elegant, and the combinatorial lemmas (Lemma 4.1, Lemma 5.1, Lemma 5.2) are proved with standard probabilistic and anti-concentration arguments rather than being black-boxed. However, two load-bearing gaps in the current write-up prevent the result from being established as stated: the proof requires a joint independence/composability property of the strong coin that Definition 1.1 does not supply, and the liveness argument for the final aggregation step is inconsistent with the paper's own strongly adaptive adversary model. The paper is a good candidate for publication after these issues are repaired.

major comments (2)
  1. [Section 5, Lemma 5.4 and proof of Theorem 2.1] The proof of Lemma 5.4 asserts: 'where the bits b1,...,bq for the q committees are independent.' This independence is load-bearing: Lemma 5.2 is applied to X = Σ bi to obtain anti-concentration. But Definition 1.1 only gives, per instance, a probability at least δ that the honest outputs equal a fresh uniform bit; it does not give a joint distribution over q concurrent instances on overlapping committees under one adaptive adversary. The cited ideal common-coin functionality [14] would supply the needed independence only if Cstr is proved to realize that functionality under concurrent composition, which is neither stated in Definition 1.1 nor proved for the concrete coins from [22], [1], [6] used in Section 6. Without independence, the adversary could correlate committee outputs, and X could be far more concentrated than a binomial, so the bound Pr[∧_i g_i=1] ≥ 1−(1−δ)^q would not imply
  2. [Section 5, liveness proof, Lines 16-20] The liveness argument states that 'the parties in H* broadcasting bits ensures that every honest party i receives |H*| ≥ 2n/3+1 bits by the time T+5.' This is false in the paper's strongly adaptive model (Section 3), where the adversary may corrupt a party after it sends a message and drop that message. The adversary can use its t corruptions to drop messages from t of the n−t honest senders, leaving a given honest recipient with as few as n−2t delivered honest messages. For t > n/6, n−2t < 2n/3+1, so the adversary can prevent the condition on Line 19 from ever being satisfied even if all honest parties have sent their Line-16 broadcasts. This breaks the liveness guarantee of T(Cstr,z,k,ε,α). The final aggregation step needs a robust mechanism (or a different channel/liveness assumption) that survives adaptive message dropping.
minor comments (4)
  1. [Definition 1.1] The definition is explicitly informal and does not state any composition or independence property across concurrent instances. Since the proof of Theorem 2.1 needs a joint guarantee over q overlapping instances, the formal version of the assumption should be given in the theorem statement or the definition, not left to a parenthetical remark about ideal functionalities.
  2. [Appendix, Lemmas 4.1 and 5.1] Both lemmas are proved by the probabilistic method, but the protocols require the parties to know the resulting bipartite graph and committee list. Please clarify whether an explicit/deterministic construction is intended, or whether the parties are assumed to have non-uniform advice; if the latter, this should be stated in the model and complexity claims.
  3. [Section 6, Ccrypto complexity] The expression 'O(n^{7/3}ε^{-6}z^{-3}n^{7/3} log n)' appears to contain a duplicated n^{7/3} factor; it should presumably be 'O(n^{7/3}ε^{-6}z^{-3} log n)'. The perfect-security expression also has an unmatched parenthesis.
  4. [Appendix, Lemma 4.1 proof] In the proof of Lemma 4.1, the sentence about a counterexample set B says vertices in V have at least Δ/2 neighbors 'in V'; this should be 'in B'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the weak coin's guarantees are derived from the assumed δ-fairness of an external strong coin; self-citations are prior published building blocks.

full rationale

The paper's central claim, Theorem 2.1, is a transformation result: it takes as an explicit input a δ-fair strong binary coin Cstr with stated cost and latency bounds, and derives the fairness, fault tolerance, cost, and latency of the transformed weak coin from those inputs. The fairness proof is a probabilistic argument (Lemma 5.4) that combines the assumed per-instance good event probability δ with an anti-concentration bound on a binomial sum; it does not rename the input as the output. There are no fitted parameters presented as predictions. The construction's use of committees as virtual parties is explicitly attributed to Bracha's earlier work and improved by removing message duplication, so it is not a renaming of a known result. The self-citations to the authors' prior work [31] are used for crusader agreement, approximate agreement, and termination as published building blocks; they are not used to justify the target claim, and no uniqueness assertion or ansatz is smuggled in through a self-citation. The main caveat—that Lemma 5.4 assumes the committee coin bits b1,...,bq are independent, while Definition 1.1 states per-instance δ-fairness—is a potential assumption/composability gap rather than a circular reduction: the theorem's conclusion does not follow merely by definition, and the independence is asserted rather than derived from the stated input. Under the review standard for circularity, this is a correctness concern, not a circularity step, so the score is low.

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

All tunable parameters (z, k, ε, α, δ, δ') are explicit inputs to the theorems rather than hidden fitted values; there is no empirical fitting. The central claim rests on prior strong-coin/AVSS protocols and standard concentration inequalities. No new entities are postulated.

assumptions (5)
  • domain assumption Existence of a δ-fair strong binary common coin Cstr with communication M(n)=O(n^k), latency R, tolerating t<αn adaptive faults; supplied by [22] Monte Carlo framework with AVSS [1] or [6].
    Theorem 2.1 takes Cstr as a black box; Cperfect/Ccrypto correctness depends on these external protocols' security.
  • standard math The hypergeometric distribution can be represented as a sum of independent (not identically distributed) Bernoulli random variables [26].
    Used in the Chernoff tail bounds in the proofs of Lemma 4.1 and Lemma 5.1.
  • domain assumption The Monte Carlo framework of [22] yields strong coins with the stated fairness, communication, and latency when instantiated with the AVSS and binding gather protocols.
    Section 6 relies on this framework; the paper does not reprove it.
  • domain assumption Crusader agreement and approximate agreement protocols from [31] achieve the stated costs: O(s^2) messages and 3 latency with <s/3 byzantine, and O(n^3 log(n/(1-δ))) messages with t<n/3.
    Publish and the perfect strong coin use these self-cited building blocks.
  • standard math Standard Chernoff bounds for sums of independent Bernoulli variables.
    Used to control the probability of bad events in the probabilistic-method proofs of Lemmas 4.1 and 5.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Subcubic Coin Tossing in Asynchrony without PKI." pith.science (2026). https://pith.science/paper/VKVDVMPE

@misc{pith2026260302071,
  author       = {Pith},
  title        = {Pith review of: Subcubic Coin Tossing in Asynchrony without PKI},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VKVDVMPE}},
  note         = {Machine review of arXiv:2603.02071}
}
abstract

We consider an asynchronous network of $n$ parties connected to each other via secure channels, up to $t$ of which are byzantine. We study common coin tossing, a task where the parties try to agree on an unpredictable random value, with some chance of failure due to the byzantine parties' influence. Coin tossing is a well-known and often-studied task due to its use in byzantine agreement. In this work, we present a committee-based method to transform strong (rarely failing) binary common coins into weaker ones that asymptotically require less communication. For any $k > 2$ and $\varepsilon > 0$, we can transform a strong binary coin that costs $\widetilde{O}(n^k)$ bits of communication into a weak binary coin that costs $\widetilde{O}(\varepsilon^{-2k}n^{3 - 2/k})$ bits. This latter coin tolerates $\varepsilon n$ fewer byzantine parties than the strong coin it is based on, and it fails with an arbitrarily small constant probability. With our method, we obtain a secure-channel-based perfectly secure coin for $t \leq (\frac{1}{4} - \varepsilon)n$ faults that costs $\widetilde{O}(n^{2.5})$ bits, as well as a coin based on cryptographic hashing for $t \leq (\frac{1}{3} - \varepsilon)n$ faults that costs $\widetilde{O}(n^{7/3}\kappa)$ bits. These are to our knowledge the first PKI-free asynchronous common coins that cost $o(n^3)$ bits of communication but still succeed with at least constant probability against $t = \Theta(n)$ adaptive byzantine faults.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 5 canonical work pages

  1. [14]

    Concurrent asynchronous byzantine agreement in expected-constant rounds, revisited

    Ran Cohen, Pouyan Forghani, Juan Garay, Rutvik Patel, and Vassilis Zikas. Concurrent asynchronous byzantine agreement in expected-constant rounds, revisited. In Guy Rothblum and Hoeteck Wee, editors,Theory of Cryptography, pages 422–451, Cham, 2023. Springer Nature Switzerland. doi:10.1007/978-3-031-48624-1_16

    work page doi:10.1007/978-3-031-48624-1_16 2023

  2. [22]

    Distributed Randomness from Approximate Agreement

    Luciano Freitas, Petr Kuznetsov, and Andrei Tonkikh. Distributed Randomness from Approximate Agreement. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing (DISC 2022) , volume 246 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 24:1–24:21, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum ...

    work page doi:10.4230/lipics.disc.2022.24 2022

  3. [1]

    Asynchronous agreement on a core set in constant expected time and more efficient asynchronous vss and mpc

    Ittai Abraham, Gilad Ashsarov, Arpita Patra, and Gilad Stern. Asynchronous agreement on a core set in constant expected time and more efficient asynchronous vss and mpc. In Theory of Cryptography: 22nd International Conference, TCC 2024, Milan, Italy, December 2–6, 2024, Proceedings, Part IV , page 451–482, Berlin, Heidelberg, 2024. Springer-Verlag. doi:1...

    work page doi:10.1007/978-3-031-78023-3_15 2024

  4. [2]

    Nearly quadratic asynchronous distributed key generation

    Ittai Abraham, Renas Bacho, Julian Loss, and Gilad Stern. Nearly quadratic asynchronous distributed key generation. Cryptology ePrint Archive, Paper 2025/006, 2025. URL: https://eprint.iacr.org/2025/006

    2025

  5. [3]

    Asynchronous agreement part 4: Crusader agreement and binding crusader agreement

    Ittai Abraham, Naama Ben-David, and Sravya Yandamuri. Asynchronous agreement part 4: Crusader agreement and binding crusader agreement. Decentralized Thoughts, 2022. URL: https://decentralizedthoughts.github.io/2022-04-05- aa-part-four-CA-and-BCA/. 14 Mose Mizrahi and Roger Wattenhofer

    2022

  6. [4]

    Asynchronous algorand: Reaching agreement with near linear communication and constant expected time

    Ittai Abraham, Eli Chouatt, Yossi Gilad, Gilad Stern, and Sophia Yakoubov. Asynchronous algorand: Reaching agreement with near linear communication and constant expected time. In Proceedings of the ACM Symposium on Principles of Distributed Computing , PODC ’25, page 28–38, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733533

    arXiv 2025

  7. [5]

    Reaching consensus for asynchronous distributed key generation

    Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. Reaching consensus for asynchronous distributed key generation. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC ’21, page 363–373, New York, NY, USA, 2021. Association for Computing Machinery.doi:10.1145/ 3465084.3467914

    arXiv 2021

  8. [7]

    Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols

    Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing , PODC ’83, page 27–30, New York, NY, USA, 1983. Association for Computing Machinery. doi:10.1145/800221.806707

    arXiv 1983

Show all 39 references
  1. [8]

    Laerebog i matematisk analyse

    Harald August Bohr and Johannes Mollerup. Laerebog i matematisk analyse. J. Gjellerups, 1920

    1920

  2. [9]

    An o(lg n) expected rounds randomized byzantine generals protocol

    G Bracha. An o(lg n) expected rounds randomized byzantine generals protocol. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , STOC ’85, page 316–326, New York, NY, USA, 1985. Association for Computing Machinery. doi:10.1145/22145.22180

    1985

  3. [11]

    An o(log n) expected rounds randomized byzantine generals protocol

    Gabriel Bracha. An o(log n) expected rounds randomized byzantine generals protocol. J. ACM, 34(4):910–920, 8 1987. doi:10.1145/31846.42229

    1987

  4. [12]

    Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract)

    Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantipole: practical asynchronous byzantine agreement using cryptography (extended abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing , PODC ’00, page ...

  5. [13]

    Fast asynchronous byzantine agreement with optimal resilience

    Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing , STOC ’93, page 42–51, New York, NY, USA, 1993. Association for Computing Machinery. doi:10.1145/167088.167105

    1993

  6. [15]

    Asynchronous consensus without trusted setup or public-key cryptography

    Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, and Victor Shoup. Asynchronous consensus without trusted setup or public-key cryptography. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS ’24, page 3242–3256, New Yor...

    2024

  7. [16]

    Diffie and M

    W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory , 22(6):644–654,

  8. [17]

    The byzantine generals strike again

    Danny Dolev. The byzantine generals strike again. Journal of Algorithms , 3(1):14–30, 1982. doi:10.1016/0196- 6774(82)90004-9

    1982 doi

  9. [18]

    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, 5 1986. doi:10.1145/5925.5931

    1986

  10. [19]

    Asymptotic expansions of central binomial coefficients and catalan numbers.J

    Neven Elezovic. Asymptotic expansions of central binomial coefficients and catalan numbers.J. Integer Seq., 17(2):14.2.1,

  11. [20]

    Dragon: Decentralization at the cost of representation after arbitrary grouping and its applications to sub-cubic dkg and interactive consistency

    Hanwen Feng, Zhenliang Lu, and Qiang Tang. Dragon: Decentralization at the cost of representation after arbitrary grouping and its applications to sub-cubic dkg and interactive consistency. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing , PODC ...

    2024

  12. [21]

    Fischer, Nancy A

    Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, 4 1985. doi:10.1145/3149.214121

    1985

  13. [23]

    Some elementary inequalities relating to the gamma and incomplete gamma function

    Walter Gautschi. Some elementary inequalities relating to the gamma and incomplete gamma function. Journal of Mathematics and Physics, 38(1-4):77–81, 1959. doi:10.1002/sapm195938177

    1959 doi

  14. [24]

    A tight lower bound on adaptively secure full-information coin flip

    Iftach Haitner and Yonatan Karidi-Heller. A tight lower bound on adaptively secure full-information coin flip. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 1268–1276, 2020. doi: 10.1109/FOCS46700.2020.00120

    2020

  15. [25]

    Byzantine agreement with optimal resilience via statistical fraud detection

    Shang-En Huang, Seth Pettie, and Leqi Zhu. Byzantine agreement with optimal resilience via statistical fraud detection. J. ACM, 71(2), 4 2024. doi:10.1145/3639454

    2024 doi

  16. [26]

    Stefen Hui and C. J. Park. The representation of hypergeometric random variables using independent bernoulli random variables. Communications in Statistics - Theory and Methods , 43(19):4103–4108, 2014. doi:10.1080/03610926.2012. 705941

    2014

  17. [27]

    Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani

    Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, and Vishal Sanwalani. Fast asynchronous byzantine agreement and leader election with full information. ACM Trans. Algorithms, 6(4), 9 2010. doi:10.1145/1824777.1824788

    2010

  18. [28]

    The multiplicative version of azuma’s inequality, with an application to contention analysis, 2025

    William Kuszmaul and Qi Qi. The multiplicative version of azuma’s inequality, with an application to contention analysis, 2025. arXiv:2102.05077

    2025 arXiv

  19. [29]

    The byzantine generals problem

    Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 7 1982. doi:10.1145/357172.357176

    1982

  20. [30]

    Quantum Byzantine Agreement Against Full-Information Adversary

    Longcheng Li, Xiaoming Sun, and Jiadong Zhu. Quantum Byzantine Agreement Against Full-Information Adversary. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing (DISC 2024) , volume 319 of Leibniz International Proceedings in Informatics (LIPIcs) , p...

    2024 doi

  21. [31]

    Asynchronous Approximate Agreement with Quadratic Communication

    Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous Approximate Agreement with Quadratic Communication. In Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci-Piergiovanni, editors, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) ,...

    2025 doi

  22. [32]

    Signature-free asynchronous binary byzantine consensus with t < n/3, o(n2) messages, and o(1) expected time

    Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary byzantine consensus with t < n/3, o(n2) messages, and o(1) expected time. J. ACM, 62(4), September 2015. doi:10.1145/2785953

    2015 doi

  23. [33]

    The evolution of quantum secure direct communication: On the road to the qinternet

    Dong Pan, Gui-Lu Long, Liuguo Yin, Yu-Bo Sheng, Dong Ruan, Soon Xin Ng, Jianhua Lu, and Lajos Hanzo. The evolution of quantum secure direct communication: On the road to the qinternet. Commun. Surveys Tuts., 26(3):1898–1949, 7

    1949

  24. [34]

    Pease, R

    M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228–234, 4 1980. doi:10.1145/322186.322188

    1980

  25. [35]

    A theoretical take on a practical consensus protocol

    Victor Shoup. A theoretical take on a practical consensus protocol. Cryptology ePrint Archive, Paper 2024/696, 2024. URL: https://eprint.iacr.org/2024/696

    2024

  26. [36]

    Randomized byzantine agreements

    Sam Toueg. Randomized byzantine agreements. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC ’84, page 163–178, New York, NY, USA, 1984. Association for Computing Machinery. doi:10.1145/800222.806744

    1984

  27. [37]

    Welch and Hagit Attiya.Distributed computing: fundamentals, simulations and advanced topics

    Jennifer L. Welch and Hagit Attiya.Distributed computing: fundamentals, simulations and advanced topics. McGraw-Hill, Inc., USA, 1998

    1998

  28. [38]

    A. D. Wyner. The wire-tap channel. The Bell System Technical Journal , 54(8):1355–1387, 1975. doi:10.1002/j.1538- 7305.1975.tb02040.x. A SKIPPED PROOFS Lemma 4.1. For all integers𝑛,𝑑 ≥ 1 and all𝑠∈[ 𝑛], there is some bipartite graph(𝑄,𝑉,𝐸) with the partite sets𝑄 of size𝑠 and𝑉 o...

    1975

  29. [1976]

    doi:10.1109/TIT.1976.1055638

    1976

  30. [2014]

    URL: https://cs.uwaterloo.ca/journals/JIS/VOL17/Elezovic/elezovic5.html

  31. [2024]

    doi:10.1109/COMST.2024.3367535

    2024

Pith tools

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