pith. sign in

arxiv: 2606.18220 · v1 · pith:SIHS36QUnew · submitted 2026-06-16 · 💻 cs.CR · cs.DC

Gatling: Rapid-Fire Consensus from Parallel Composition

Pith reviewed 2026-06-26 23:44 UTC · model grok-4.3

classification 💻 cs.CR cs.DC
keywords atomic broadcastconsensusparallel compositioninter-proposal timeblockchainlatency optimizationrotating leaders
0
0 comments X

The pith

Gatling achieves arbitrarily small inter-proposal times by running multiple staggered instances of any black-box atomic broadcast protocol.

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

The paper establishes that consensus performance in fault-free executions is limited by how often proposals can be issued, not just by how fast each one is confirmed. Gatling composes multiple copies of an existing atomic broadcast protocol, offsets their leader schedules, and applies a fixed rule to merge their outputs into one ordered log. This construction allows proposals to appear in succession faster than a single network delay. The authors also calculate the best number of copies when crashed leaders cause head-of-line blocking and show that the method works with unmodified component protocols.

Core claim

Gatling runs multiple parallel instances of a black-box atomic broadcast protocol and staggers their proposal schedules to generate proposals in faster succession than state-of-the-art protocols. A deterministic interleaving rule merges the outputs of these instances into a single global log. The protocol achieves arbitrarily small inter-proposal times under rotating leader schedules while preserving safety and liveness.

What carries the argument

Staggered parallel instances of a black-box atomic broadcast protocol with a deterministic interleaving rule that merges their outputs into one consistent log

If this is right

  • Inter-proposal times can be driven below one network delay under rotating leaders.
  • The optimal number of parallel instances follows from an analysis of head-of-line blocking.
  • Two variants of the construction retain predictable validity.
  • Off-the-shelf atomic broadcast protocols can be used directly without latency-specific tuning.

Where Pith is reading between the lines

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

  • The same parallel-composition idea could be applied to protocols whose confirmation latency is already close to the lower bound.
  • Adaptive selection of the number of instances might improve performance when failure rates vary.
  • The interleaving rule may affect other properties such as fairness or censorship resistance in ways not analyzed here.

Load-bearing premise

The deterministic interleaving rule merges outputs from the parallel instances while preserving both safety and liveness of the black-box protocol.

What would settle it

An execution in which a leader crash causes the merged log to lose total order or to stop making progress would falsify the central claim.

Figures

Figures reproduced from arXiv: 2606.18220 by Giulia Scaffino, Joachim Neu, Max Resnick.

Figure 1
Figure 1. Figure 1: The Gatling protocol depicted in this figure runs [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The Gatling protocol Π G depicted in this figure runs 𝐾 = 4 instances of a component protocol Π c . The union of the proposal sequences of Π c 1 (red), Π c 2 (blue), Π c 3 (magenta), Π c 4 (orange) is the 𝑇ipt/4-spaced proposal sequence of Π G. We denote by λ𝑗 [𝑖] the payload confirmed in the 𝑖-th slot of the 𝑗-th instance. The Gatling log λ at time 𝑡 ≥ GST is reconstructed at the top as the concatenation … view at source ↗
Figure 3
Figure 3. Figure 3: Behavior of Gatling in the presence of an adversarial proposer. Left: Each component instance assigns a leader per [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Optimal Gatling global inter-proposal spacing [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison between the empty-blocks Gatling (top) and a PBFT-style protocol (bottom), both instantiated with a [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Subprime-blocks variant of Gatling that restores predictable validity at execution. At the top, the consensus confirma [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: the transaction latency is minimized at 𝐾 = 9 for the 1% drop rate, at 𝐾 = 4 for the 5% drop rate, and at 𝐾 = 3 for the 10% drop rate. In the right panel of [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 7
Figure 7. Figure 7: Transaction latency as a function of 𝐾 across three proposal drop rate regimes: 10% (left), 5% (center), and 1% (right). Each bar decomposes total latency into the proposal wait time (blue), representing the Gatling inter-proposal time 𝜖, and the finality wait time (orange), representing the confirmation time 𝑇conf . The more reliable the validator set is, the more concurrent instances can be tolerated wit… view at source ↗
read the original abstract

Consensus protocols form the core of blockchains and other replicated state machines, ensuring that all correct nodes process the same totally ordered log of input transactions. In fault-free executions, performance is driven by the good-case transaction latency -- the time between a transaction becoming known to all nodes and its confirmation by the consensus protocol -- which depends on both how frequently proposals are made and, once made, how quickly they are confirmed. While prior work has established tight lower bounds on confirmation latency that modern protocols already achieve, it remains open whether the inter-proposal time can be further reduced below the state-of-the-art of one network delay. We introduce Gatling, an atomic broadcast protocol that achieves arbitrarily small inter-proposal times under rotating leader schedules; in particular, smaller than the network delay. Gatling runs multiple parallel instances of a black-box atomic broadcast protocol and staggers their proposal schedules to generate proposals in faster succession than state-of-the-art protocols. A deterministic interleaving rule merges the outputs of these instances into a single global log. We analyze the effects of head-of-line blocking caused by crashed leaders, and derive Gatling's optimal number of parallel instances. We further study the impact of Gatling on predictable validity and present two variants that retain this property. Finally, our experiments confirm that Gatling can be used with off-the-shelf component protocols to achieve low latency without fine-tuning the component protocol for minimum latency.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper introduces Gatling, an atomic broadcast protocol that runs multiple parallel instances of a black-box atomic broadcast protocol with staggered proposal schedules. A deterministic interleaving rule merges their outputs into a single totally ordered log, enabling arbitrarily small inter-proposal times (below one network delay) under rotating leader schedules. The work analyzes head-of-line blocking from crashed leaders to derive an optimal number of instances, studies impacts on predictable validity with two variants, and validates the approach experimentally with off-the-shelf component protocols.

Significance. If the central claims hold, Gatling addresses an open performance question in consensus by reducing inter-proposal spacing below the network delay bound while inheriting safety and liveness from black-box components. This could improve good-case latency in blockchains and replicated state machines without requiring protocol-specific tuning. The black-box composition and experimental results with existing protocols are notable strengths for practical adoption.

major comments (2)
  1. [Protocol construction and interleaving rule] The deterministic interleaving rule (described in the protocol construction) must be shown to preserve both safety and liveness of the underlying black-box atomic broadcast instances when a leader crash occurs in one instance. The skeptic concern is load-bearing: if the rule admits a scenario where a single crash stalls the global log for longer than the per-instance confirmation latency, the arbitrarily-small inter-proposal claim fails even under rotating leaders.
  2. [HOL blocking analysis] § on head-of-line blocking analysis and optimal k derivation: the analysis must explicitly demonstrate that the merged schedule delivers proposals at the claimed rate for the derived optimal number of instances under the failure model (including leader crashes). The current outline does not provide a concrete bound or counterexample check showing that no single crash violates the inter-proposal spacing guarantee.
minor comments (2)
  1. [Analysis section] Clarify the exact failure model (e.g., crash-stop vs. Byzantine) assumed for the optimal-k derivation and rotating-leader case.
  2. [Experiments] The experiments section would benefit from explicit comparison tables showing inter-proposal times against the cited state-of-the-art baselines.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. The two major comments correctly identify areas where the presentation of safety/liveness preservation and the HOL analysis can be strengthened with more explicit arguments. We will revise the manuscript to incorporate formal lemmas, concrete bounds, and verification steps as detailed below.

read point-by-point responses
  1. Referee: [Protocol construction and interleaving rule] The deterministic interleaving rule (described in the protocol construction) must be shown to preserve both safety and liveness of the underlying black-box atomic broadcast instances when a leader crash occurs in one instance. The skeptic concern is load-bearing: if the rule admits a scenario where a single crash stalls the global log for longer than the per-instance confirmation latency, the arbitrarily-small inter-proposal claim fails even under rotating leaders.

    Authors: We agree that an explicit demonstration is required. The interleaving rule assigns each instance's outputs to fixed, non-overlapping positions in the global log based solely on instance index and round number; this is independent of intra-instance timing or content. Consequently, safety (total order within each instance) and liveness (eventual progress per instance) are inherited directly. A crash in one instance affects only its slots, which continue to be populated by the remaining instances under the staggered rotating-leader schedule. We will add a dedicated lemma (with proof sketch) in the revised protocol section proving that, under the rotating-leader model, no single crash can stall the merged log beyond one per-instance confirmation latency, thereby preserving the sub-network-delay inter-proposal guarantee. revision: yes

  2. Referee: [HOL blocking analysis] § on head-of-line blocking analysis and optimal k derivation: the analysis must explicitly demonstrate that the merged schedule delivers proposals at the claimed rate for the derived optimal number of instances under the failure model (including leader crashes). The current outline does not provide a concrete bound or counterexample check showing that no single crash violates the inter-proposal spacing guarantee.

    Authors: The existing HOL analysis models a worst-case stall of one instance for its full confirmation latency and selects the smallest k such that the staggered schedules still deliver proposals at the target rate. We acknowledge that the current text would benefit from greater explicitness. In the revision we will insert a theorem giving the precise delivery-rate bound (1/k network delay in the presence of one crash) together with a short counterexample verification confirming that, for the derived optimal k, no single crash produces a spacing violation. This will make the derivation self-contained and directly responsive to the concern. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation relies on external black-box properties

full rationale

The paper constructs Gatling by composing multiple parallel instances of an external black-box atomic broadcast protocol, applying a deterministic interleaving rule, and analyzing head-of-line blocking to select the number of instances. All load-bearing claims inherit safety and liveness from the assumed properties of the black-box components rather than redefining or fitting them internally. No equations reduce a derived quantity to a fitted parameter by construction, no self-citation chain justifies the central interleaving rule, and the optimal-k derivation is presented as an analysis of the given failure model rather than an ansatz smuggled in or a renamed known result. The derivation is therefore self-contained against the stated external assumptions.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; full details unavailable.

free parameters (1)
  • optimal number of parallel instances
    Derived from head-of-line blocking analysis.
axioms (1)
  • domain assumption Black-box atomic broadcast protocol satisfies standard safety and liveness.
    Required for the parallel composition to inherit correctness.

pith-pipeline@v0.9.1-grok · 5781 in / 1110 out tokens · 31924 ms · 2026-06-26T23:44:45.240406+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

55 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    Ittai Abraham and Kartik Nayak. 2022. What is Responsiveness? https: //decentralizedthoughts.github.io/2022-12-18-what-is-responsiveness/

  2. [2]

    Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case Latency of Byzantine Broadcast: a Complete Categorization. InPODC. ACM, 331–341

  3. [3]

    Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dion- ysis Zindros. 2025. pod: An Optimal-Latency, Censorship-Free, and Accounta- ble Generalized Consensus Layer. InDISC (LIPIcs, Vol. 356). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 4:1–4:24

  4. [4]

    Kaya Alpturer, Kushal Babel, and Aditya Saraf. 2025. Timing Games in Responsive Consensus Protocols. arXiv:2510.25144v1 [cs.GT]

  5. [5]

    Anza. 2024. Alpenglow: A New Consensus for Solana. https://www .anza.xyz/ blog/alpenglow-a-new-consensus-for-solana

  6. [6]

    Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman

  7. [7]

    Shoal++: High Throughput DAG BFT Can Be Fast and Robust!. InNSDI. USENIX Association, 813–826

  8. [8]

    Lynch, and Larry J

    Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1994. Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. J. ACM41, 1 (1994), 122–152

  9. [9]

    Kushal Babel, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Arun Koshy, Alberto Sonnino, and Mingwei Tian. 2025. Mys- ticeti: Reaching the Latency Limits with Uncertified DAGs. InNDSS. The Internet Society

  10. [10]

    Sam Blackshear, Andrey Chursin, George Danezis, Anastasios Kichidis, Lefteris Kokoris-Kogias, Xun Li, Mark Logan, Ashok Menon, Todd Nowacki, Alberto Sonnino, Brandon Williams, and Lu Zhang. 2024. Sui Lutris: A Blockchain Combining Broadcast and Consensus. InCCS. ACM, 2606–2620

  11. [11]

    2016.Tendermint: Byzantine Fault Tolerance in the Age of Blockchains

    Ethan Buchman. 2016.Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. Master’s thesis. University of Guelph. https:// atrium.lib.uoguelph.ca/items/5459099e-67aa-4a23-83ae-d3471d8d8336

  12. [12]

    Vitalik Buterin. 2014. Ethereum: A Next-Generation Smart Contract and Decen- tralized Application Platform. https://ethereum.org/whitepaper/

  13. [13]

    Vitalik Buterin and Virgil Griffith. 2019. Casper the Friendly Finality Gadget. arXiv:1710.09437v4 [cs.CR]

  14. [14]

    Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In OSDI. USENIX Association, 173–186

  15. [15]

    Celestia. 2023. Celestia: Modular Blockchain Network. https://celestia.org/

  16. [16]

    Chan and Rafael Pass

    Benjamin Y. Chan and Rafael Pass. 2023. Simplex Consensus: A Simple and Fast Consensus Protocol. InTCC (4) (Lecture Notes in Computer Science, Vol. 14372). Springer, 452–479

  17. [17]

    Chan and Elaine Shi

    Benjamin Y. Chan and Elaine Shi. 2020. Streamlet: Textbook Streamlined Blockchains. InAFT. ACM, 1–11

  18. [18]

    ChorusOne. 2024. Post on X. https://x .com/ChorusOne/status/ 1955615856580301252

  19. [19]

    Brendan Kobayashi Chou, Andrew Lewis-Pye, and Patrick O’Grady. 2026. Min- immit: Fast Finality with Even Faster Blocks. arXiv:2508.10862v1 [cs.DC]

  20. [20]

    Commonware. 2024. Commonware Alto. https://github .com/commonwarexyz/ alto. GitHub repository

  21. [21]

    Commonware. 2024. Commonware Monorepo. https://github .com/ commonwarexyz/monorepo. GitHub repository

  22. [22]

    George Danezis, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman. 2022. Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus. InEuroSys. ACM, 34–50

  23. [23]

    Isaac Doidge, Raghavendra Ramesh, Nibesh Shrestha, and Joshua Tobkin. 2024. Moonshot: Optimizing Block Period and Commit Latency in Chain-Based Rotat- ing Leader BFT. InDSN. IEEE, 470–482

  24. [24]

    Lynch, and Larry J

    Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1988. Consensus in the presence of partial synchrony.J. ACM35, 2 (1988), 288–323

  25. [25]

    Pranav Garimidi, Joachim Neu, and Max Resnick. 2025. Multiple Concurrent Proposers: Why and How. Cryptology ePrint Archive, Paper 2025/1772. https: //eprint.iacr.org/2025/1772

  26. [26]

    Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. 2022. Jolteon and Ditto: Network-Adaptive Efficient Con- sensus with Asynchronous Fallback. InFinancial Cryptography (Lecture Notes in Computer Science, Vol. 13411). Springer, 296–315

  27. [27]

    Amir Herzberg and Shay Kutten. 2000. Early Detection of Message Forwarding Faults.SIAM J. Comput.30, 4 (2000), 1169–1196

  28. [28]

    Dakai Kang, Suyash Gupta, Dahlia Malkhi, and Mohammad Sadoghi. 2025. HotStuff-1: Linear Consensus with One-Phase Speculation.Proc. ACM Manag. Data3, 3 (2025), 171:1–171:29

  29. [29]

    Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman

  30. [30]

    All You Need is DAG. InPODC. ACM, 165–175

  31. [31]

    Lucianna Kiffer, Joachim Neu, Srivatsan Sridhar, Aviv Zohar, and David Tse

  32. [32]

    Nakamoto Consensus under Bounded Processing Capacity. InCCS. ACM, 363–377

  33. [33]

    Hanzheng Lyu, Shaokang Xie, Jianyu Niu, Chen Feng, Yinqian Zhang, and Ivan Beschastnikh. 2025. Ladon: High-Performance Multi-BFT Consensus via Dynamic Global Ordering. InEuroSys. ACM, 226–242

  34. [34]

    Dahlia Malkhi and Kartik Nayak. 2023. Extended Abstract: HotStuff-2: Optimal Two-Phase Responsive BFT. Cryptology ePrint Archive, Paper 2023/397. https: //eprint.iacr.org/2023/397

  35. [35]

    Dahlia Malkhi, Chrysoula Stathakopoulou, and Maofan Yin. 2024. BBCA-Chain: Low Latency, High Throughput BFT Consensus on a DAG. InFC (1) (Lecture Notes in Computer Science, Vol. 14744). Springer, 51–73

  36. [36]

    Jean-Philippe Martin and Lorenzo Alvisi. 2006. Fast Byzantine Consensus.IEEE Trans. Dependable Secur. Comput.3, 3 (2006), 202–215

  37. [37]

    Satoshi Nakamoto. 2009. Bitcoin: A Peer-to-Peer Electronic Cash System. https: //bitcoin.org/bitcoin.pdf. 14 Gatling: Rapid-Fire Consensus from Parallel Composition

  38. [38]

    Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse, and Mohammad Alizadeh

  39. [39]

    Longest Chain Consensus Under Bandwidth Constraint. InAFT. ACM, 126–147

  40. [40]

    Joachim Neu, Ertem Nusret Tas, and David Tse. 2022. The Availability- Accountability Dilemma and Its Resolution via Accountability Gadgets. InFi- nancial Cryptography (Lecture Notes in Computer Science, Vol. 13411). Springer, 541–559

  41. [41]

    Rafael Pass and Elaine Shi. 2017. Hybrid Consensus: Efficient Consensus in the Permissionless Model. InDISC (LIPIcs, Vol. 91). Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 39:1–39:16

  42. [42]

    Alejandro Ranchal-Pedrosa, Benjamin Marsh, Lefteris Kokoris-Kogias, and Al- berto Sonnino. 2025. Sedna: Sharding Transactions in Multiple Concurrent Proposer Blockchains. arXiv:2512.17045v1 [cs.CR]

  43. [43]

    Caspar Schwarz-Schilling, Fahad Saleh, Thomas Thiery, Jennifer Pan, Nihar Shah, and Barnabé Monnot. 2023. Time Is Money: Strategic Timing Games in Proof- Of-Stake Protocols. InAFT (LIPIcs, Vol. 282). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 30:1–30:17

  44. [44]

    Victor Shoup. 2024. Sing a Song of Simplex. InDISC (LIPIcs, Vol. 319). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37:1–37:22

  45. [45]

    Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen. 2025. Kudzu: Fast and Simple High-Throughput BFT. InDISC (LIPIcs, Vol. 356). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 42:1–42:19

  46. [46]

    Nibesh Shrestha and Aniket Kate. 2025. Hydrangea++: Enhancing Hydrangea with Optimistic Proposals. https://supra .com/documents/hydrangea-plus- plus.pdf

  47. [47]

    Nibesh Shrestha, Aniket Kate, and Kartik Nayak. 2025. Hydrangea: Optimistic Two-Round Partial Synchrony with Improved Fault Resilience. Cryptology ePrint Archive, Paper 2025/1112. https://eprint.iacr.org/2025/1112

  48. [48]

    Alexander Spiegelman, Balaji Arun, Rati Gelashvili, and Zekun Li. 2024. Shoal: Improving DAG-BFT Latency and Robustness. InFC (1) (Lecture Notes in Com- puter Science, Vol. 14744). Springer, 92–109

  49. [49]

    Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris- Kogias. 2022. Bullshark: DAG BFT Protocols Made Practical. InCCS. ACM, 2705–2718

  50. [50]

    Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolic

  51. [51]

    Mir-BFT: Scalable and Robust BFT for Decentralized Networks.J. Syst. Res.2, 1 (2022)

  52. [52]

    Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolic. 2022. State machine replication scalability made simple. InEuroSys. ACM, 17–33

  53. [53]

    Thomas Thiery, Francesco D’Amato, Julian Ma, Barnabé Monnot, Terence Tsao, Jacob Kaufmann, and Jihoon Song. 2024. EIP-7805: Fork-choice En- forced Inclusion Lists (FOCIL). Ethereum Improvement Proposals. https: //eips.ethereum.org/EIPS/eip-7805

  54. [54]

    Anatoly Yakovenko. 2018. Solana: A new architecture for a high performance blockchain v0.8.13. https://solana.com/solana-whitepaper.pdf

  55. [55]

    Reiter, Guy Golan-Gueta, and Ittai Abra- ham

    Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abra- ham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In PODC. ACM, 347–356. A Deferred Proofs Proof of Thm. 4.1. Safety.For any two arbitrary honest nodes 𝑝 and 𝑞, and any two arbitrary points in time 𝑡 and ˜𝑡, let λ be the log output by 𝑝 at time 𝑡 and ˜λ the ...