Gatling: Rapid-Fire Consensus from Parallel Composition
Pith reviewed 2026-06-26 23:44 UTC · model grok-4.3
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.
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
- 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
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.
Referee Report
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)
- [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.
- [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)
- [Analysis section] Clarify the exact failure model (e.g., crash-stop vs. Byzantine) assumed for the optimal-k derivation and rotating-leader case.
- [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
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
-
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
-
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
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
free parameters (1)
- optimal number of parallel instances
axioms (1)
- domain assumption Black-box atomic broadcast protocol satisfies standard safety and liveness.
Reference graph
Works this paper leans on
-
[1]
Ittai Abraham and Kartik Nayak. 2022. What is Responsiveness? https: //decentralizedthoughts.github.io/2022-12-18-what-is-responsiveness/
2022
-
[2]
Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case Latency of Byzantine Broadcast: a Complete Categorization. InPODC. ACM, 331–341
2021
-
[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
2025
- [4]
-
[5]
Anza. 2024. Alpenglow: A New Consensus for Solana. https://www .anza.xyz/ blog/alpenglow-a-new-consensus-for-solana
2024
-
[6]
Balaji Arun, Zekun Li, Florian Suri-Payer, Sourav Das, and Alexander Spiegelman
-
[7]
Shoal++: High Throughput DAG BFT Can Be Fast and Robust!. InNSDI. USENIX Association, 813–826
-
[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
1994
-
[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
2025
-
[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
2024
-
[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]
Vitalik Buterin. 2014. Ethereum: A Next-Generation Smart Contract and Decen- tralized Application Platform. https://ethereum.org/whitepaper/
2014
-
[13]
Vitalik Buterin and Virgil Griffith. 2019. Casper the Friendly Finality Gadget. arXiv:1710.09437v4 [cs.CR]
work page internal anchor Pith review Pith/arXiv arXiv 2019
-
[14]
Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In OSDI. USENIX Association, 173–186
1999
-
[15]
Celestia. 2023. Celestia: Modular Blockchain Network. https://celestia.org/
2023
-
[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
2023
-
[17]
Chan and Elaine Shi
Benjamin Y. Chan and Elaine Shi. 2020. Streamlet: Textbook Streamlined Blockchains. InAFT. ACM, 1–11
2020
-
[18]
ChorusOne. 2024. Post on X. https://x .com/ChorusOne/status/ 1955615856580301252
2024
- [19]
-
[20]
Commonware. 2024. Commonware Alto. https://github .com/commonwarexyz/ alto. GitHub repository
2024
-
[21]
Commonware. 2024. Commonware Monorepo. https://github .com/ commonwarexyz/monorepo. GitHub repository
2024
-
[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
2022
-
[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
2024
-
[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
1988
-
[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
2025
-
[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
2022
-
[27]
Amir Herzberg and Shay Kutten. 2000. Early Detection of Message Forwarding Faults.SIAM J. Comput.30, 4 (2000), 1169–1196
2000
-
[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
2025
-
[29]
Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman
-
[30]
All You Need is DAG. InPODC. ACM, 165–175
-
[31]
Lucianna Kiffer, Joachim Neu, Srivatsan Sridhar, Aviv Zohar, and David Tse
-
[32]
Nakamoto Consensus under Bounded Processing Capacity. InCCS. ACM, 363–377
-
[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
2025
-
[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
2023
-
[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
2024
-
[36]
Jean-Philippe Martin and Lorenzo Alvisi. 2006. Fast Byzantine Consensus.IEEE Trans. Dependable Secur. Comput.3, 3 (2006), 202–215
2006
-
[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
2009
-
[38]
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse, and Mohammad Alizadeh
-
[39]
Longest Chain Consensus Under Bandwidth Constraint. InAFT. ACM, 126–147
-
[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
2022
-
[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
2017
- [42]
-
[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
2023
-
[44]
Victor Shoup. 2024. Sing a Song of Simplex. InDISC (LIPIcs, Vol. 319). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 37:1–37:22
2024
-
[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
2025
-
[46]
Nibesh Shrestha and Aniket Kate. 2025. Hydrangea++: Enhancing Hydrangea with Optimistic Proposals. https://supra .com/documents/hydrangea-plus- plus.pdf
2025
-
[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
2025
-
[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
2024
-
[49]
Alexander Spiegelman, Neil Giridharan, Alberto Sonnino, and Lefteris Kokoris- Kogias. 2022. Bullshark: DAG BFT Protocols Made Practical. InCCS. ACM, 2705–2718
2022
-
[50]
Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolic
-
[51]
Mir-BFT: Scalable and Robust BFT for Decentralized Networks.J. Syst. Res.2, 1 (2022)
2022
-
[52]
Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolic. 2022. State machine replication scalability made simple. InEuroSys. ACM, 17–33
2022
-
[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
2024
-
[54]
Anatoly Yakovenko. 2018. Solana: A new architecture for a high performance blockchain v0.8.13. https://solana.com/solana-whitepaper.pdf
2018
-
[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 ...
2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.