Pith. sign in

REVIEW 2 major objections 3 minor 66 references

Scalable Byzantine Reliable Broadcast (Extended Version)

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

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

Pith's one-line read The paper claims the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation, replacing quorums with private random samples and accepting small quantified failure probabilities.

desk verdict A strong protocol with reusable analysis, but Lemma 26 has a load-bearing parameter error that must be fixed before the logarithmic-consistency claim is credible. read the letter →

arxiv 1908.01738 v3 pith:YCRB7E2O submitted 2019-08-05 cs.DC

Rachid Guerraoui , Petr Kuznetsov , Matteo Monti , Matej Pavlovic , Dragos-Adrian Seredinschi , Yann Vonlanthen This is my paper · ORCID
classification cs.DC MSC 68M1468W1568W20
keywords Byzantinereliablebroadcastprobabilisticstochasticsamplesgossipprotocolsadversarydecoratorsthresholdcontagionlogarithmiccommunicationcomplexityasynchronousdistributedsystems
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 sets out to prove that Byzantine reliable broadcast—the primitive that lets a group of processes agree on a sender's message despite some members, possibly including the sender, being malicious—can be made scalable. Its protocol, Contagion, replaces the traditional quorum, whose size is linear in the number of processes $N$, with small random samples, and accepts that each broadcast property (validity, consistency, totality) fails with a fixed probability $\epsilon$ that the analysis bounds. The central claim is that for any fixed $\epsilon$ the per-process communication and computation stay $O(\log N)$, with $O(\log N / \log\log N)$ latency, and that for realistic parameters the failure probability is around $10^{-16}$ with thousands of processes. If correct, this is the first logarithmic-cost Byzantine reliable broadcast under an asynchronous model with a static Byzantine adversary.

What carries the argument

The load-bearing object is the private stochastic sample, replacing quorums: each process randomly selects $O(\log N)$ peers for gossip, echo, ready, and delivery roles, relying on Chernoff-type concentration instead of intersection guarantees. Around this, two analysis tools carry the proof: adversary decorators, which transform any Byzantine adversary into a stronger one within a smaller class (ultimately two-phase adversaries) so that bounding failure under the restricted class bounds it for all adversaries; and Threshold Contagion, a game on a random multigraph that models how 'ready for message $m$' spreads through correct processes and shows the adversary's strategy cannot bias the final infection count. The ready threshold being lower than the delivery threshold is the mechanism that produces the all-or-none totality behavior.

What would settle it

Build the protocol on a network where the adversary can observe message metadata (no onion routing or private messaging) and run the numerical parameter regime claimed to give $10^{-16}$; if the adversary can then bias the ready or delivery sample of a single targeted correct process—for instance, by sending subscriptions that fill that process's sample with Byzantine identities—and the measured probability of a consistency or totality violation exceeds the claimed $\epsilon$, the analysis's core privacy assumption is violated.

Watch

Extended reading notes

Core claim

The paper's central discovery is a probabilistic generalization of Byzantine reliable broadcast plus an algorithm achieving it: each correct process uses private random samples instead of intersecting quorums, and the protocol is shown $\epsilon$-secure with $\epsilon$ arbitrarily small. Murmur provides probabilistic broadcast by gossip; Sieve provides consistency through echo samples and an adversarial analysis that reduces the set of strategies to 'two-phase adversaries' via adversary decorators; Contagion adds totality using a ready/delivery threshold feedback loop modeled as a Threshold Contagion game, in which the adversary's choices provably do not bias the infection process. The combined result: per-process communication and computation $O(\log N)$, latency $O(\log N / \log\log N)$, and numerical violation probabilities of order $10^{-16}$ for systems of thousands of processes. The analysis claims the first formal treatment of a probabilistic broadcast protocol under Byzantine faults, and the first logarithmic-complexity Byzantine reliable broadcast.

Load-bearing premise

The whole failure analysis assumes the Byzantine adversary never learns which correct processes communicate with one another—equivalently, that it cannot see or poison the private random samples of any targeted correct process—so the uniform sampling on which every bound rests stays hidden from it.

Editorial extensions

If this is right

  • Byzantine reliable broadcast becomes practical at thousands of processes with per-node cost $O(\log N)$ and near-negligible failure probability, if the sampling and privacy assumptions hold.
  • A Byzantine sender cannot make two correct processes deliver different messages except with probability $\epsilon$, and cannot cause some-but-not-all correct delivery except with probability $\epsilon$.
  • Failure probability decays exponentially in average sample size and grows at most quadratically in $N$, so keeping $\epsilon$ fixed forces sample sizes to grow logarithmically.
  • Latency is $O(\log N / \log\log N)$, comprising gossip dissemination plus two extra message delays for echo and ready rounds.
  • The same sample-based replacement for quorums can be applied to other quorum-based primitives, reducing their communication from linear to logarithmic at the price of probabilistic guarantees.

Reading between the lines

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

  • Editorial inference: if the private-sampling assumption can be enforced cheaply via anonymous communication, the logarithmic complexity should transfer to permissionless settings with churn, since the paper's sampling oracle is already designed for membership-free systems.
  • Editorial inference: the adversary-decorator method is a general recipe for bounding failure probabilities by shrinking the adversary's strategy space, and could be reused for other probabilistic consensus primitives.
  • Editorial inference: the threshold separation $\hat{R}/R < \hat{D}/D$ is a tunable knob the paper fixes; varying the gap should trade a larger critical infected fraction for a lower totality failure probability, which an implementation could exploit.
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 / 3 minor

Summary. The paper introduces a probabilistic relaxation of Byzantine reliable broadcast in which each property (validity, consistency, totality) may fail with probability at most epsilon. It presents three protocols: Murmur, a gossip-based probabilistic broadcast; Sieve, an echo-based probabilistic consistent broadcast; and Contagion, a feedback-based probabilistic reliable broadcast that combines Sieve with a ready/delivery sample mechanism. Samples drawn from a uniform private sampling oracle replace quorums, giving O(log N) per-process communication and O(log N / log log N) latency for fixed epsilon. The main technical contributions are adversary decorators, used to reduce the Sieve adversary to a tractable two-phase form, and the Threshold Contagion game, used to analyze the Contagion feedback loop. The paper claims the first Byzantine reliable broadcast protocol with logarithmic per-process communication complexity in the asynchronous model with a static Byzantine adversary, with numerical failure probabilities around 10^-16.

Significance. If the analysis is correct, this is a substantial result: it replaces quorum intersection with representative random samples and provides an end-to-end probabilistic security argument for Byzantine reliable broadcast in a setting where previous protocols had linear per-process complexity. The manuscript is unusually detailed for an extended version: elementary properties (no duplication, integrity, Murmur totality via Erdos-Renyi connectivity) are proved cleanly, and the decorator framework is an original proof technique that may be reusable beyond this paper. The Threshold Contagion model is also a valuable abstraction for gossip-style feedback mechanisms. The paper does not provide machine-checked proofs or executable code, and the numerical section is not reproducible from the text; those are weaknesses in presentation rather than in the core analytic method. The central issue is a load-bearing inconsistency in the Contagion consistency proof, described below.

major comments (2)
  1. [Appendix C.7, Lemma 26; Appendix E.3; Theorem 13] Lemma 26 is inconsistent with the Threshold Contagion model it invokes. The lemma claims P[rho] = P[gamma(N,R,0,1,N-C,hatR) = rho+(N-C)] for an execution in which no correct process pcb.Delivers m and every Byzantine process sends Ready(m) to every correct process that subscribed to it. Under the paper's own definition, l is the probability that each of the R predecessor slots exists; l=0 yields an edge-free multigraph, so no healthy node can ever reach threshold hatR and gamma is identically N-C. The right-hand side is therefore a point mass at rho=0. The protocol, however, has a positive probability of correct processes becoming ready: already with N=3, C=2, R=1, hatR=1, a correct process's single ready sample is Byzantine with probability f=1/3, and that Byzantine process sends Ready(m) to it, so P[rho>0] = 1-(2/3)^2 = 5/9. This contradicts the claimed distribution. Lemma 25's analogous reduction correctly uses l=1-f for the correct-only graph; Lemma 26 needs l=1, because every ready-sample slot is occupied and Byzantine predecessors act as initially infected nodes. Since Theorem 13 builds the consistency bound mu on gamma+, the stated bound is unsupported until Lemma 26 is corrected and the subsequent formulas in Theorem 13 are re-derived.
  2. [Section 2; Appendices B and C] The privacy and uniformity of the sampling oracle are load-bearing assumptions that are not connected to a concrete implementation by any theorem. Section 2 assumes the adversary never learns which correct processes communicate with one another and cites onion routing, private messaging, and the BRAHMS sampling oracle [10], but no result states that those mechanisms provide exactly uniform, independent samples that remain hidden from a static Byzantine adversary. The decorator reductions in Appendix B and the sample-blind adversary argument in particular rely on the adversary seeing only the Byzantine membership of samples, not the samples themselves. If an implementation allows even one sample to be biased or observed, the Chernoff-based bounds in Theorems 9 and 14 no longer follow. Please either state formally that the ideal private uniform oracle is a modeling assumption and scope the practical claims accordingly, or supply a composition proof with [10] and the private-communication layer.
minor comments (3)
  1. [Section 6 and Figure 2] The numerical evaluation does not report the concrete parameter values used (G, E, R, D, the four thresholds, N, f) and does not provide code or data. A short table of the parameter settings and an artifact link would make the claimed 10^-16 failure probabilities checkable.
  2. [Appendix C.1, totality definition] The definition of epsilon-totality contains the typo 'probabiity'; it should read 'probability'.
  3. [Appendix B.6.2 and Algorithm 5] The Byzantine oracle Psi is an artificial assumption used only for Simplified Sieve; the paper explicitly says no correct process invokes Psi during Sieve. This is acceptable, but the text should state once more, right before Theorem 9, that the final bound does not depend on Psi being implementable.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the probabilistic bounds are derived from explicit sample-size and threshold inequalities, and the only self-citations are contextual, not load-bearing.

full rationale

The paper's central derivation is self-contained rather than circular. Murmur's totality bound rests on the standard Erdos-Renyi connectivity phase transition, citing external results [1,17]. Sieve's consistency bound is obtained by introducing a strictly weaker strawman (Simplified Sieve), proving via decorators in Appendix D that an optimal adversary lies in a tractable class, and then deriving explicit binomial and Chernoff bounds in Theorem 9. Contagion's consistency and totality bounds are reduced to the Threshold Contagion game analyzed in Appendix E, and Theorems 12-14 express the failure probability as explicit functions of the sample sizes R,D, thresholds Rhat,Dhat, Byzantine fraction f, and system size N. No quantity needed for the advertised epsilon is produced by fitting a parameter to the same property it is then used to predict; the sample sizes are inputs and the bounds are outputs. The authors' self-citations ([32], and gossip references [2,26,27] in related work) are contextual and do not justify any uniqueness, optimality, or correctness claim. The sampling oracle [10] and onion-routing/private-messaging mechanisms [18,52] are external implementation assumptions rather than self-citations that define the result. The proof issue flagged for Lemma 26 -- using link probability l=0 for an execution in which Byzantine predecessors do send Ready messages -- is a potential internal inconsistency in a reduction, not a circularity: it does not make Theorem 13's conclusion equal to an input by construction. Accordingly, no circular step is exhibited and the score is near the bottom of the scale.

Assumptions & free parameters 7 free parameters · 6 assumptions · 2 invented entities

The central claims rest on standard probabilistic machinery, the asynchronous Byzantine model, and a strong privacy assumption about the sampling oracle. The analysis also introduces two proof devices, adversary decorators and Threshold Contagion, which are not physical entities. No new physical particles, forces, or conserved quantities are introduced.

free parameters (7)
  • G = not fitted (design parameter)
    Expected gossip sample size in Murmur; must be Θ(log N) for connectivity with high probability; chosen by security target.
  • E = not fitted (design parameter)
    Echo sample size in Sieve; controls total validity and consistency; chosen with Ehat.
  • Ehat = not fitted (design parameter)
    Delivery threshold in Sieve; must exceed the expected Byzantine share of a sample.
  • R = not fitted (design parameter)
    Ready sample size in Contagion; controls the contagion threshold and feedback loop.
  • Rhat = not fitted (design parameter)
    Contagion threshold in Contagion; ratio Rhat/R must be below Dhat/D for totality.
  • D = not fitted (design parameter)
    Delivery sample size in Contagion; controls delivery probability and validity.
  • Dhat = not fitted (design parameter)
    Delivery threshold in Contagion; must be above the contagion threshold fraction.
assumptions (6)
  • standard math Standard Chernoff bounds and Erdős-Rényi connectivity and diameter results.
    Used in Section 3.2, Appendices A and B, and Lemma 10 to bound sample deviations and gossip graph connectivity.
  • domain assumption Asynchronous message-passing with reliable authenticated point-to-point links.
    Section 2 defines the model; all protocols rely on eventual delivery and unforgeable signatures.
  • domain assumption Static Byzantine adversary controlling a fixed fraction f of processes.
    Section 2 assumes the adversary is fixed at the start and does not adaptively change the faulty set.
  • domain assumption Uniform, independent sampling oracle Omega and adversary ignorance of correct processes' random choices and communication patterns.
    Section 2 states this; it is load-bearing because the probabilistic bounds depend on samples being uniform and unknown to the adversary.
  • ad hoc to paper Byzantine oracle Psi in Simplified Sieve: correct processes can identify Byzantine processes.
    Appendix B.6.2 introduces Psi as an analytical device; the authors explicitly state it is unsatifiable in practice but used only to upper-bound the real adversary's power.
  • ad hoc to paper The adversarial execution of Contagion is equivalent to a Threshold Contagion game on a random multigraph.
    Appendices C.7 and E assert this equivalence; it is the basis for the consistency and totality bounds and is itself one of the paper's main analytical claims.
invented entities (2)
  • Adversary decorators
    purpose: Proof technique to reduce arbitrary Byzantine adversaries to a tractable class without changing the upper bound on failure probability.
    A mathematical construct, not an observable entity; its validity is internal to the proofs in Appendix D.
  • Threshold Contagion game
    purpose: Abstraction of ready-message propagation in Contagion; used to bound consistency and totality failure probabilities.
    A mathematical model; its predictive value is realized only through the paper's theorems, not through independent empirical evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scalable Byzantine Reliable Broadcast (Extended Version)." pith.science (2026). https://pith.science/paper/YCRB7E2O

@misc{pith2026190801738,
  author       = {Pith},
  title        = {Pith review of: Scalable Byzantine Reliable Broadcast (Extended Version)},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YCRB7E2O}},
  note         = {Machine review of arXiv:1908.01738}
}
read the original abstract

Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as they typically build on quorum systems with strong intersection guarantees, which results in linear per-process communication and computation complexity. We generalize the Byzantine reliable broadcast abstraction to the probabilistic setting, allowing each of its properties to be violated with a fixed, arbitrarily small probability. We leverage these relaxed guarantees in a protocol where we replace quorums with stochastic samples. Compared to quorums, samples are significantly smaller in size, leading to a more scalable design. We obtain the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation complexity. We conduct a complete and thorough analysis of our protocol, deriving bounds on the probability of each of its properties being compromised. During our analysis, we introduce a novel general technique we call adversary decorators. Adversary decorators allow us to make claims about the optimal strategy of the Byzantine adversary without having to make any additional assumptions. We also introduce Threshold Contagion, a model of message propagation through a system with Byzantine processes. To the best of our knowledge, this is the first formal analysis of a probabilistic broadcast protocol in the Byzantine fault model. We show numerically that practically negligible failure probabilities can be achieved with realistic security parameters.

Figures

Figures reproduced from arXiv: 1908.01738 by the authors.

Figure 1
Figure 1. A possible instance of a Threshold Contagion game. Black nodes represent currently infected nodes, grey nodes will get infected in the next step as at least Rˆ = 2 of their predecessors are infected. At the beginning of each round, the player infects a subset of the healthy nodes. In the rest of the round, the infection (analogous to the readiness for a message) propagates as follows. A healthy node that reaches a c… view at source ↗
Figure 2
Figure 2. Left – -security of Contagion, as a function of the average sample size S = hG, E, R, Di. We use a system size of 1024 processes and fractions of tolerated Byzantine processes f = 0.1 and f = 0.15. Right – Square root of the normalized -security of Contagion, as a function of the system size N, for various fractions of Byzantine processes (f) and average sample sizes (S). We normalize the values in each series by … view at source ↗
Figure 3
Figure 3. An execution without decorator. pcb adversary padv pcb system cob adversary cob system sys Byzantine State Sample Deliver Echo End Byzantine State Deliver Echo End Init Step Init Step Trace τ cob decorator cadv [PITH_FULL_IMAGE:figures/full_fig_p066_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: A decorator exposing both its system interface to the pcb ad￾versary and its adversary interface to the cob system. • Procedure cadv.Byzantine(process) simply forwards the call to sys.Byzantine(process). • Procedure cadv.Deliver(process, message) sets deliveries[proces…
Figure 5
Figure 5. Figure 5: An illustration of the steps needed to prove that the adversarial power of α is greater than that of α 0 . whether it has been coupled directly with σ, or it has been coupled with σ 0 , with Cob decorator acting as an interface. We prove this by induction. Let us assum…
Figure 6
Figure 6. Figure 6: Two systems with (one of) their respective echo samples. The table on the right shows the permutation from sys1 to sys2. Clearly both systems are equally likely. Moreover, the effect of process 3 delivering mes￾sage 1 (grey) in sys1, is equal to process 1 delivering th…
Figure 7
Figure 7. Figure 7: An example game of Threshold Contagion. Here N = 11, l = 1, R = 3, Rˆ = 2, K = 1 and S = 3. Notice how nodes can be linked to themselves, form loops, or be linked more than once. An initial set of S nodes (1) is infected by the player (2). The game then unfolds in cont…
Figure 8
Figure 8. Figure 8: An example multigraph g = (v, e) with 7 nodes. A subset X ⊆ v is highlighted. Numbered dots represent the elements of v, and the edges to nodes 1, 2 and 3 are displayed. With R = 3 and Rˆ = 2, we have g1 ∈/ R˜X, g2 ∈ R˜X, and g3 ∈ R˜X. Note how the predecessor vector o…
Figure 9
Figure 9. Figure 9: An illustration of sample space and the steps needed to show that a contagion step defines a Markov chain. The grey arrow represents a transition from a state to another. One of the states is further partitioned by S r i . The dark grey area represents a case that we p…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 65 canonical work pages

  1. [10]

    Brahms: Byzantine resilient random membership sampling

    Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer. Brahms: Byzantine resilient random membership sampling. Computer Networks, 53(13):2340 – 2359, 2009. Gossiping in Distributed Systems

    work page 2009

  2. [1]

    6.207/14.15: Networks - lecture 4: Erd˝ os–r´ enyi graphs and phase transitions.https://economics.mit

    Daron Acemoglu and Asu Ozdaglar. 6.207/14.15: Networks - lecture 4: Erd˝ os–r´ enyi graphs and phase transitions.https://economics.mit. edu/files/4622, 2009

    work page 2009

  3. [2]

    How efficient can gossip be? (on the cost of resilient information exchange)

    Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Morteza Zadi- moghaddam. How efficient can gossip be? (on the cost of resilient information exchange). In Proceedings of the 37th International Collo- quium Conference on Automata, Languages and Programming: Part II , ICALP’10, pages 115–126, Berlin, Heidelberg, 2010. Springer-Verlag

    work page 2010

  4. [3]

    Sharing memory robustly in message-passing systems

    Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. JACM, 42(1), 1995

    work page 1995

  5. [4]

    Order optimal information spreading using algebraic gossip

    Chen Avin, Michael Borokhovich, Keren Censor-Hillel, and Zvi Lotker. Order optimal information spreading using algebraic gossip. In Pro- ceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing , PODC ’11, pages 363–372, New York, NY, USA, 2011. ACM

    work page 2011

  6. [5]

    Towards a scalable and robust DHT

    Baruch Awerbuch and Christian Scheideler. Towards a scalable and robust DHT. Theory of Computing Systems , 45(2):234–260, 2009

    work page 2009

  7. [6]

    Efficient ran- domised broadcasting in random regular networks with applications in peer-to-peer systems

    Petra Berenbrink, Robert Elsaesser, and Tom Friedetzky. Efficient ran- domised broadcasting in random regular networks with applications in peer-to-peer systems. In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing , PODC ’08, pages 155–164, New York, NY, USA, 2008. ACM

    work page 2008

  8. [7]

    Communi- cation complexity of quasirandom rumor spreading

    Petra Berenbrink, Robert Els¨ asser, and Thomas Sauerwald. Communi- cation complexity of quasirandom rumor spreading. In Proceedings of the 18th Annual European Conference on Algorithms: Part I , ESA’10, pages 134–145, Berlin, Heidelberg, 2010. Springer-Verlag

    work page 2010

Show all 66 references
  1. [8]

    Ran- domised broadcasting: Memory vs

    Petra Berenbrink, Robert Els¨ asser, and Thomas Sauerwald. Ran- domised broadcasting: Memory vs. randomness. Theoretical Computer Science, 520:306–319, 04 2010

    2010

  2. [9]

    Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu, and Yaron Minsky

    Kenneth P. Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu, and Yaron Minsky. Bimodal multicast. ACM Trans. Comput. Syst., 17(2):41–88, May 1999. 18

    1999

  3. [11]

    Communication locality in secure multi-party computation

    Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication locality in secure multi-party computation. In Theory of Cryptography, 2013

    2013

  4. [12]

    Asynchronous Byzantine agreement protocols

    Gabriel Bracha. Asynchronous Byzantine agreement protocols. Infor- mation and Computation , 75(2):130–143, 1987

    1987

  5. [13]

    Asynchronous Consensus and Broad- cast Protocols

    Gabriel Bracha and Sam Toueg. Asynchronous Consensus and Broad- cast Protocols. JACM, 32(4), 1985

    1985

  6. [14]

    Springer Publishing Company, Incorporated, 2nd edition, 2011

    Christian Cachin, Rachid Guerraoui, and Lu´ ıs Rodrigues.Introduction to Reliable and Secure Distributed Programming . Springer Publishing Company, Incorporated, 2nd edition, 2011

    2011

  7. [15]

    Christian Cachin and Jonathan A. Poritz. Secure intrusion-tolerant replication on the internet. In DSN, 2002

    2002

  8. [16]

    Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas

    Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas. The hidden graph model: Communication locality and optimal resiliency with adaptive faults. In ITCS ’15, 2015

    2015

  9. [17]

    The diameter of sparse random graphs

    Fan Chung and Linyuan Lu. The diameter of sparse random graphs. Advances in Applied Mathematics , 26:257–279, 2001

    2001

  10. [18]

    Tor: The second-generation onion router

    Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: The second-generation onion router. In Proceedings of the 13th Conference on USENIX Security Symposium - Volume 13 , SSYM’04, pages 21–21, Berkeley, CA, USA, 2004. USENIX Association

    2004

  11. [19]

    Reiter, and Haibin Zhang

    Sisi Duan, Michael K. Reiter, and Haibin Zhang. BEAT: Asynchronous BFT Made Practical. In CCS, 2018

    2018

  12. [20]

    On the influence of graph den- sity on randomized gossiping

    Robert Els¨ asser and Dominik Kaaser. On the influence of graph den- sity on randomized gossiping. 2015 IEEE International Parallel and Distributed Processing Symposium, pages 521–531, 2015

    2015

  13. [21]

    On random graphs.Publicationes Math- ematicae, 6:290–297, 1959

    Paul Erd¨ os and Alfr´ ed R´ enyi. On random graphs.Publicationes Math- ematicae, 6:290–297, 1959. 19

    1959

  14. [22]

    P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. Lightweight probabilistic broadcast. ACM Trans. Comput. Syst., 21(4):341–374, November 2003

    2003

  15. [23]

    A generic theoretical framework for modeling gossip-based algorithms

    Yaacov Fernandess, Antonio Fern´ andez, and Maxime Monod. A generic theoretical framework for modeling gossip-based algorithms. SIGOPS Oper. Syst. Rev., 41(5):19–27, October 2007

    2007

  16. [24]

    The price of low communication in secure multi-party computation

    Juan Garay, Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas. The price of low communication in secure multi-party computation. In Annual International Cryptology Conference, pages 420–446. Springer, 2017

    2017

  17. [25]

    Adaptively Secure Broadcast, Revisited

    Juan A Garay, Jonathan Katz, Ranjit Kumaresan, and Hong-Sheng Zhou. Adaptively Secure Broadcast, Revisited. In PODC, pages 179–

  18. [26]

    Kowalski

    Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski. On the complexity of asynchronous gossip. In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, pages 135–144, New York, NY, USA, 2008. ACM

    2008

  19. [27]

    Kowalski

    Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski. Asynchronous gossip. J. ACM, 60(2):11:1–11:42, May 2013

    2013

  20. [28]

    Kowalski

    Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski. Meeting the deadline: on the complexity of fault-tolerant continuous gossip. Distributed Computing, 24(5):223–244, Dec 2011

    2011

  21. [29]

    A polylogarithmic gossip algorithm for plurality consensus

    Mohsen Ghaffari and Merav Parter. A polylogarithmic gossip algorithm for plurality consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing , PODC ’16, pages 117–126, New York, NY, USA, 2016. ACM

    2016

  22. [30]

    How asyn- chrony affects rumor spreading time

    George Giakkoupis, Yasamin Nazari, and Philipp Woelfel. How asyn- chrony affects rumor spreading time. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing , PODC ’16, pages 185–194, New York, NY, USA, 2016. ACM

    2016

  23. [31]

    Highly dy- namic distributed computing with byzantine failures

    Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. Highly dy- namic distributed computing with byzantine failures. In PODC, 2013. 20

    2013

  24. [32]

    The Consensus Number of a Cryptocurrency

    Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos Seredinschi. The Consensus Number of a Cryptocurrency. In PODC, 2019. (to appear)

    2019

  25. [33]

    Fault-tolerant broadcasts and re- lated problems

    Vassos Hadzilacos and Sam Toueg. Fault-tolerant broadcasts and re- lated problems. In Sape J. Mullender, editor,Distributed Systems, chap- ter 5, pages 97–145. Addison-Wesley, 1993

    1993

  26. [34]

    Discovery through gossip

    Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Ra- jaraman, and Zhifeng Sun. Discovery through gossip. In Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Al- gorithms and Architectures, SPAA ’12, pages 140–149, New York, NY, USA, 2012. ACM

    2012

  27. [35]

    T-man: Gossip-based fast overlay topology construction

    M´ ark Jelasity, Alberto Montresor, and Ozalp Babaoglu. T-man: Gossip-based fast overlay topology construction. Comput. Netw. , 53(13):2321–2339, August 2009

    2009

  28. [36]

    Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information

    Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. InInternational Conference on Distributed Com- puting and Networking , pages 203–214. Springer, 2011

    2011

  29. [37]

    Scalable leader election

    Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In SODA, 2006

    2006

  30. [38]

    The byzantine generals problem

    Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. TOPLAS, 4(3), 1982

    1982

  31. [39]

    Gossip versus deterministically constrained flooding on small networks

    Meng-Jang Lin, Keith Marzullo, and Stefano Masini. Gossip versus deterministically constrained flooding on small networks. InProceedings of the 14th International Conference on Distributed Computing , DISC ’00, pages 253–267, London, UK, UK, 2000. Springer-Verlag

    2000

  32. [40]

    Secure Reliable Multicast Protocols in a WAN

    Dahlia Malkhi, Michael Merritt, and Ohad Rodeh. Secure Reliable Multicast Protocols in a WAN. In ICDCS, 1997

    1997

  33. [41]

    Byzantine quorum systems

    Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 569–578. ACM, 1997

    1997

  34. [42]

    Dahlia Malkhi and Michael K. Reiter. A high-throughput secure reliable multicast protocol. In CSFW, 1996. 21

    1996

  35. [43]

    Dahlia Malkhi and Michael K. Reiter. A high-throughput secure reliable multicast protocol. Journal of Computer Security , 5(2):113–128, 1997

    1997

  36. [44]

    Probabilistic quorum systems

    Dahlia Malkhi, Michael K Reiter, Avishai Wool, and Rebecca N Wright. Probabilistic quorum systems. Inf. Comput., 170(2):184–206, November 2001

    2001

  37. [45]

    Bitcoin: A peer-to-peer electronic cash system, 2008

    Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008

    2008

  38. [46]

    Handling message semantics with generic broadcast protocols

    Fernando Pedone and Andr´ e Schiper. Handling message semantics with generic broadcast protocols. Distributed Computing, 15(2):97–107, 2002

    2002

  39. [47]

    Michael K. Reiter. Secure Agreement Protocols: Reliable and Atomic Group Multicast in Rampart. In CCS, 1994

    1994

  40. [48]

    Reiter and Kenneth P

    Michael K. Reiter and Kenneth P. Birman. How to securely replicate services. ACM Transactions on Programming Languages and Systems (TOPLAS), 16(3), 1994

    1994

  41. [49]

    How to Spread Adversarial Nodes? Rotate! In STOC, pages 704–713

    Christian Scheideler. How to Spread Adversarial Nodes? Rotate! In STOC, pages 704–713. ACM, 2005

    2005

  42. [50]

    Slow links, fast links, and the cost of gossip

    Suman Sourav, Peter Robinson, and Seth Gilbert. Slow links, fast links, and the cost of gossip. 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS) , pages 786–796, 2018

    2018

  43. [51]

    Randomized byzantine agreements

    Sam Toueg. Randomized byzantine agreements. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Comput- ing, PODC ’84, pages 163–178, New York, NY, USA, 1984. ACM

    1984

  44. [52]

    Vuvuzela: Scalable private messaging resistant to traffic analy- sis

    Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zel- dovich. Vuvuzela: Scalable private messaging resistant to traffic analy- sis. In Proceedings of the 25th Symposium on Operating Systems Prin- ciples, SOSP ’15, pages 137–152, New York, NY, USA, 2015. ACM

    2015

  45. [53]

    A robust and scalable peer-to-peer gossiping protocol

    Spyros Voulgaris, M´ ark Jelasity, and Maarten van Steen. A robust and scalable peer-to-peer gossiping protocol. In Proceedings of the Sec- ond International Conference on Agents and Peer-to-Peer Computing , AP2PC’03, pages 47–58, Berlin, Heidelberg, 2004. Springer-Verlag

    2004

  46. [54]

    The origin of quorum systems

    Marko Vukolic. The origin of quorum systems. Bulletin of the EATCS , 101:125–147, 2010. 22

    2010

  47. [55]

    Zhang, K

    B. Zhang, K. Han, B. Ravindran, and E. D. Jensen. Rtqg: Real-time quorum-based gossip protocol for unreliable networks. In 2008 Third International Conference on Availability, Reliability and Security, pages 564–571, March 2008. 23 Contents 1 Introduction 1 2 Model and Assumpt...

    2008

  48. [59]

    ϵ-Totality: If a correct process delivers a message, then every correct process eventually delivers a message with probability at least (1−ϵ). A.2 Algorithm Murmur (Algorithm 1) distributes a single message across the system by means of gossip: upon reception, a correct proces...

  49. [62]

    ϵ-Total validity: If σ is correct, andσ broadcasts a messagem, every correct process eventually delivers m with probability at least (1−ϵ)

  50. [63]

    ϵ-Consistency: Every correct process that delivers a message delivers the same message with probability at least (1 −ϵ). 35 B.2 Algorithm Algorithm 2 Procedure sample 1: procedure sample(message,size ) is 2: ψ =∅; 3: for size times do 4: ψ←ψ∪ Ω(1); 5: end for 6: for all π∈ψ do...

  51. [64]

    within the context of message s, consider my Echo to be for message m

    ϵ-Consistency: With probability at least (1−ϵ), at most one message m exists, such that m is delivered by any correct process. We note how the above definition of ϵ-consistency is equivalent to the one we provided in Appendix B.1, but adapted for a context where no du- plicatio...

  52. [65]

    No duplication: No correct process delivers more than one message

  53. [66]

    Integrity: If a correct process delivers a message m, and σ is correct, then m was previously broadcast by σ

  54. [67]

    ϵ-Validity: If σ is correct, and σ broadcasts a message m, then σ eventually deliversm with probability at least (1−ϵ)

  55. [68]

    ϵ-Totality: If a correct process delivers a message, then every correct process eventually delivers a message with probabiity at least (1 −ϵ)

  56. [69]

    ϵ-Consistency: Every correct process that delivers a message delivers the same message with probability at least (1 −ϵ). 97 Algorithm 7 Contagion 1: Implements: 2: ProbabilisticReliableBroadcast, instance prb 3: 4: Uses: 5: AuthenticatedPointToPointLinks,instance al 6: Probabi...

  57. [70]

    The probability distribution underlying g is known, and we compute it in this section

    The topology of the random multigraph g on which Threshold Con- tagion is played. The probability distribution underlying g is known, and we compute it in this section

  58. [71]

    The probability distribution underlying the player’s choices is unknown and arbitrary

    The player’s infection strategy, i.e., the nodes the player chooses to infect at the beginning of each round. The probability distribution underlying the player’s choices is unknown and arbitrary. In this section, we only formalize their sample space. Thus, an element of the s...

Pith tools

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