Pith. sign in

REVIEW 3 major objections 5 minor 28 references

Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding

T0 review · 3 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A distributed scheduler for sharded blockchains keeps transaction queues bounded at a near-optimal worst-case injection rate.

desk verdict The multi-leader result is not proven: the central Lemma 5.3 is a sketch, and Theorem 5.5 should not be cited as a stability bound until the schedule-control delay argument is made rigorous. read the letter →

arxiv 2509.02421 v1 pith:WADN4GKK submitted 2025-09-02 cs.DC

Ramesh Adhikari , Costas Busch , Dariusz R. Kowalski This is my paper · ORCID
classification cs.DC
keywords BlockchainShardingTransactionSchedulingPartialSynchronyAdversarialStabilityLocality-basedClusteringboundedlatencyqueuingtheorydistributed
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 asks how fast transactions can be injected into a sharded blockchain without letting pending queues or latency grow without bound, under a worst-case adversary that can choose when and where transactions appear. It proposes two event-driven schedulers: a single-leader version and a multi-leader version using layered shard clustering. The multi-leader result is the main achievement: for rho up to (1/(16 c1 log D log s)) * max(1/k, 1/ceil(sqrt(s))), every transaction commits within bounded time and the total number of pending transactions is bounded by 2(2b + rho * 48 c1 D delay log D log s) * s. Since the absolute ceiling for any scheduler is max(2/(k+1), 2/floor(sqrt(2s))), this bound is within a poly-log factor of optimal, and it works in a partially synchronous model rather than requiring full synchrony. Stability under adversarial traffic is what protects a sharded system from denial-of-service-style congestion.

What carries the argument

Two event-driven schedulers. A leader shard maintains a pending queue, builds a transaction conflict graph (edges connect transactions sharing an accessed account), colors it greedily, and uses the color count as the schedule length; a scheduling event triggers when this length reaches the previously recorded length. Version numbers tag batches to match account-state responses under partial synchrony. For the distributed version, a sparse-cover clustering partitions the shard graph into O(log D) layers and O(log s) sub-layers; each cluster has a leader and a schedule-control token acquired from child clusters. The analysis divides time into intervals and proves by induction that transactions

What would settle it

Run Algorithm 2 on a small shard graph with a leaky-bucket adversary injecting just below the stated rate; if any cluster leader's schedule-control wait exceeds one schedule length per layer and sublayer, or if combined pending queues exceed 2(2b+rho*48*c1*d*log D log s)s, the claimed bound fails.

Watch

Extended reading notes

Core claim

The paper claims two stability results. The single-leader scheduler (Algorithm 1) is stable for rho <= max{1/(16k), 1/(16*ceil(sqrt(s)))}, keeping combined pending transactions bounded by 2(2b + rho*48*d)s and transaction latency at most 32b*min{k,sqrt(s)} + 96d. The multi-leader scheduler (Algorithm 2) achieves stability for rho <= (1/(16 c1 log D log s)) * max{1/k, 1/ceil(sqrt(s))}, with pending transactions bounded by 2(2b + rho*48*c1*d*log D log s)s and latency by 32*c1*b*log D log s * min{k,sqrt(s)} + 96*c1*d*log D log s, with d an upper bound on processing and communication delay and D the shard graph diameter. Since the optimal possible rate is max{2/(k+1), 2/floor(sqrt(2s))}, the mul

Load-bearing premise

The multi-leader stability bound rests on the assumption that a cluster leader's total wait for scheduling control is at most the sum of the single-cluster scheduling times over all c1 log D log s layers and sublayers below it, an assertion the paper states rather than derives from the control-token flow, with c1 never quantified.

Editorial extensions

If this is right

  • At injection rates up to the stated thresholds, queue sizes and transaction latency remain bounded no matter how the adversary arranges injections, so the system cannot be forced into unbounded backlog.
  • The multi-leader scheduler improves on the best previous distributed result by removing the linear dependence of the stable rate on the maximum shard distance d; the rate now depends only on the shard graph diameter through log D.
  • The multi-leader stable rate is within a poly-logarithmic factor of the absolute upper bound for any scheduler, making it near-optimal in the worst-case adversarial model.
  • The schedule-control hierarchy is deadlock-free because cluster heights are lexicographically ordered and control flows only from lower to higher heights, so every generated transaction eventually commits or aborts within bounded time.
  • The single-leader scheduler extends stability guarantees from a synchronous clique network to a general partially synchronous shard graph with diameter D, with queue and latency bounds depending on the delay bound d rather than on graph topology.

Reading between the lines

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

  • If c1 were made explicit, the bounds could be directly checked by simulation: a natural test is to run Algorithm 2 under a leaky-bucket adversary near the stated rate and compare the maximum combined pending queue to the theorem's formula.
  • The stability argument relies mainly on the sparse-cover clustering properties, so a periodic refresh of the clustering that preserves those properties may extend the result to dynamic shard membership without redoing the proof.
  • Because the model treats communication congestion through a generic delay bound d, the scheduling analysis could be layered on top of adversarial routing bounds for the network, yielding end-to-end stability guarantees for the full system.
  • The rate's independence from transaction distance suggests that on high-diameter shard graphs the log D factor is the main price of locality; quantifying c1 would show whether this price is acceptable in practice.
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

3 major / 5 minor

Summary. The paper studies stability of transaction processing in sharded blockchains under an adversarial leaky-bucket injection model with rate ρ and burstiness b. It proposes two event-driven schedulers. Algorithm 1 (single leader) claims stability for ρ ≤ max{1/(16k), 1/(16⌈√s⌉)}, with combined pending queues bounded by 2(2b+ρ·48𝔇)s and transaction latency at most 32b·min{k,√s}+96𝔇, in a partially synchronous model with delay bound 𝔇. Algorithm 2 (multi-leader) uses a hierarchical clustering of the shard graph and claims stability for ρ ≤ 1/(16c₁ log D log s)·max{1/k, 1/⌈√s⌉}, with analogous queue and latency bounds. The multi-leader result is advertised as within a polylog factor of the optimum and a significant improvement over the prior result in [2]. The analysis divides time into fixed-length intervals, bounds the number of transactions generated per interval, uses greedy graph coloring to bound per-interval schedule lengths, and inducts over intervals to prove that transactions are committed by the end of the following interval.

Significance. If the results are correct, they would constitute a meaningful improvement: the multi-leader injection rate would no longer depend linearly on the transaction distance d (only logarithmically on the shard-graph diameter D), and the protocol would work under partial synchrony rather than full synchrony, matching the optimal rate up to polylog factors. The single-leader extension to general graph diameter D is also a step beyond the clique-graph assumption of [2]. The paper gives explicit formulas for queue bounds and latency, and the single-leader scheduler is conceptually simple, based on greedy coloring and versioned batches. However, the central supporting lemmas contain substantial proof gaps: the single-leader induction does not correctly handle batches that combine transactions from two intervals, and the multi-leader analysis relies on an unproven assertion about schedule-control delay. Thus the advertised near-optimality is not established in the current manuscript.

major comments (3)
  1. [§4.1, Lemma 4.3, Cases 2.a and 2.b] The induction step does not account for the fact that the last scheduling event E_X of interval I_z can contain both T_A (transactions from I_{z-1} not yet committed) and T_B (transactions generated in I_z up to E_X); together these can be as large as 2ζ. Lemma 4.2 only applies to at most ζ pending transactions. The proof adds τ/4 for T_A and τ/4 for T_B as if they were processed sequentially, but Algorithm 1 (lines 16–18) moves all pending transactions into one batch and processes them together; the schedule length of the union is never bounded. Consequently property (ii) — that all transactions generated in I_z commit by the end of I_{z+1} — is unsupported, and the latency bound in Theorem 4.4 rests on this induction.
  2. [§5.3, Lemma 5.3] This lemma is the linchpin of the multi-leader result, but it is asserted rather than derived from Algorithm 2. The proof states that since there are c₁ log D log s sublayers, the total scheduling length from cluster C and all descendant clusters is at most (τ′/(4c₁ log D log s))·c₁ log D log s = τ′/4. This multiplication is circular without establishing that each sublayer contributes at most one scheduling length. Algorithm 2's control flow (lines 31–46) allows a child to use schedule control for its own transactions while a parent is waiting, and control requests are forwarded recursively; nothing bounds the queueing delay of control requests or the number of acquisitions per level. The constant c₁ is never quantified, so the theorem's rate is not explicit. Lemma 5.4 is stated as following 'the same structure' as Lemma 4.3, so it inherits both this gap and the two-batch gap from the si
  3. [Section 6, Conclusions] The statement that 'no confirmation step from destination shards is required in our schedulers' contradicts the algorithms. Algorithm 1 lines 30–32 and 41 explicitly wait for final_commit_response before removing a transaction from SQ and before reducing LastEventSchLength; Algorithm 2 line 18 similarly waits until all transactions are committed before releasing schedule control. If the intended claim is that there is no separate confirmation round-trip beyond the pre-commit batch, the text should say precisely that; as written, the claim is false and could mislead readers about the protocol's behavior.
minor comments (5)
  1. [Theorem 5.5 and Lemma 5.2] The injection rate in Theorem 5.5 is written as max{1/k, 1/√s} with no ceiling on √s, while the abstract and Table 1 use ⌈√s⌉. Lemma 5.2 Case 2 has the same inconsistency. Please align the notation.
  2. [Lemma 5.2 proof] The proof refers to 'Equation 5.3' in the proof of Lemma 5.1, but no such equation is numbered. It should refer to 'the proof of Lemma 5.1' or to the displayed inequality in that proof.
  3. [Algorithm 2, line 17] The pseudocode says 'Process all transactions T′ of SQ using Algorithm 1,' but Algorithm 1 is a standalone event-driven scheduler, not a subroutine that can be invoked on an already-formed schedule queue. The interaction between the control-acquisition mechanism and the internal events of Algorithm 1 needs to be specified precisely.
  4. [Proof of Theorem 5.6] There is a typo: 's𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝐶𝑜𝑛𝑡𝑟𝑜𝑙' should be '𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒𝐶𝑜𝑛𝑡𝑟𝑜𝑙'.
  5. [Theorem 4.4 and abstract] Theorem 4.4 states latency with min{k,√s}, while the abstract uses min{k,⌈√s⌉}. These should be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the stability bounds are derived from the stated adversarial model and do not reduce to fitted parameters or to load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained rather than circular. The single-leader scheduler is analyzed by dividing time into intervals of length tau and bounding the number of transactions zeta generated per interval under the leaky-bucket adversary (Lemma 4.1). Lemma 4.2 then bounds the time to commit zeta transactions from the conflict-graph coloring degree, using only the injection-rate assumption rho <= rho'. Lemma 4.3 is an induction over intervals, and Theorem 4.4 combines these bounds. No fitted parameter is renamed as a prediction, and the rate rho is an assumption, not an output of a fit. The multi-leader analysis (Section 5) follows the same shape: Lemmas 5.1 and 5.2 redo the single-cluster bounds with an explicit constant c1, and Lemma 5.3 aggregates over the O(log D log s) layers/sublayers. The constant c1 is a free explicit constant in the statement—it is not chosen after measuring the target quantity—so this is not a fitted-input-called-prediction pattern. The main weakness is that Lemma 5.3 asserts, rather than derives from Algorithm 2's request/release event flow, that the total schedule-control delay is at most the sum of per-cluster scheduling lengths over all layers/sublayers; Lemma 5.4 explicitly says its proof is the same as Lemma 4.3 with Lemma 5.3 substituted. That is a significant correctness/rigor gap, but it is not circularity: the asserted delay bound does not assume Theorem 5.5 or the queue/latency bounds being proved. Likewise, the conclusion's claim that 'no confirmation step is required' appears inconsistent with the final_commit_response events in Algorithms 1 and 2, but that is an internal consistency issue, not a circular reduction. The self-citations to [2] are used for model conventions and as the comparison baseline, while the clustering toolkit [16] is external; no load-bearing result is justified solely by a same-author citation, and no uniqueness theorem or ansatz is imported from the authors' prior work. Overall, no enumerated circularity pattern can be exhibited by quoting an equation that reduces to its own input.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central stability results rest on the adversarial injection model, partial synchrony with bounded delay D_delay, and the existence of a sparse-cover clustering with O(log D log s) levels. The only parameter introduced by the analysis is the unspecified constant c1, and the only ad hoc modeling choice is unit-time graph construction/coloring.

free parameters (1)
  • c1
    Positive constant in the multi-leader injection rate and latency bounds; never given a value or derived from the clustering parameters. Absorbs all O(log D log s) overhead in Lemma 5.3.
assumptions (6)
  • domain assumption Leaky bucket adversary: in any interval of length t, congestion at any shard <= rho * t + b.
    Section 3, Adversarial Model; defines the stability problem and the injection-rate parameter.
  • domain assumption Partial synchrony with GST and known bound D_delay on processing plus communication delay after GST.
    Section 3, Communication Model; used to size intervals tau and tau'.
  • domain assumption Cluster decomposition of G_s with O(log D) layers and O(log s) sublayers satisfying sparse-cover properties from [16].
    Section 5.1; used to argue control-acquisition overhead is O(log D log s).
  • standard math Greedy vertex coloring uses at most Delta+1 colors, and commit time of a color class is unit time.
    Lemma 4.2 proof; the whole latency bound rests on the coloring bound.
  • ad hoc to paper Leader can construct and color the conflict graph in one time unit regardless of pending queue size.
    Lemma 4.2, 'leader shard takes 1 time unit for graph construction and coloring'; a modeling simplification not justified by the size of the graph.
  • domain assumption Each shard runs Byzantine consensus with n_i > 3 f_i and messages between shards are reliably delivered via cluster sending.
    Section 3, Communication Model; needed for the safety claims but safety proofs are not detailed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding." pith.science (2026). https://pith.science/paper/WADN4GKK

@misc{pith2026250902421,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WADN4GKK}},
  note         = {Machine review of arXiv:2509.02421}
}
abstract

In blockchain sharding, $n$ processing nodes are divided into $s$ shards, and each shard processes transactions in parallel. A key challenge in such a system is to ensure system stability for any ``tractable'' pattern of generated transactions; this is modeled by an adversary generating transactions with a certain rate of at most $\rho$ and burstiness $b$. This model captures worst-case scenarios and even some attacks on transactions' processing, e.g., DoS. A stable system ensures bounded transaction queue sizes and bounded transaction latency. It is known that the absolute upper bound on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions is $\max\left\{ \frac{2}{k+1}, \frac{2}{ \left\lfloor\sqrt{2s}\right\rfloor}\right\}$, where $k$ is the maximum number of shards that each transaction accesses. Here, we first provide a single leader scheduler that guarantees stability under injection rate $\rho \leq \max\left\{ \frac{1}{16k}, \frac{1}{16\lceil \sqrt{s} \rceil}\right\}$. Moreover, we also give a distributed scheduler with multiple leaders that guarantees stability under injection rate $\rho \leq \frac{1}{16c_1 \log D \log s}\max\left\{ \frac{1}{k}, \frac{1}{\lceil \sqrt{s} \rceil} \right\}$, where $c_1$ is some positive constant and $D$ is the diameter of shard graph $G_s$. This bound is within a poly-log factor from the optimal injection rate, and significantly improves the best previous known result for the distributed setting by Adhikari et al., SPAA 2024.

Figures

Figures reproduced from arXiv: 2509.02421 by the authors.

Figure 1
Figure 1. Simple representation of scheduling event triggered [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [16]

    Anupam Gupta, Mohammad T Hajiaghayi, and Harald Räcke. 2006. Oblivious network design. In Proc. of the 17th ACM-SIAM Symp. on Discrete Algorithms (SODA’06). 970–979

    work page 2006

  2. [2]

    Ramesh Adhikari, Costas Busch, and Dariusz R Kowalski. 2024. Stable blockchain sharding under adversarial transaction generation. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures . 451–461

    work page 2024

  3. [1]

    Ramesh Adhikari and Costas Busch. 2023. Lockless Blockchain Sharding with Multiversion Control. Springer-Verlag, Berlin, Heidelberg, 112–131

    work page 2023

  4. [3]

    Ramesh Adhikari, Costas Busch, and Miroslav Popovic. 2024. Fast Transaction Scheduling in Blockchain Sharding. arXiv preprint arXiv:2405.15015 (2024)

    work page Pith review arXiv 2024

  5. [4]

    Ramesh Adhikari, Costas Busch, and Miroslav Popovic. 2025. On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding. arXiv preprint arXiv:2508.07472 (2025). Proceedings of the 39th International Symposium on Distributed Computing

    work page Pith review arXiv 2025

  6. [5]

    Clustering via torque balance with mass and distance

    C. Alvarez, M. Blesa, and M. Serna. 2004. The impact of failure management on the stability of communication networks. In Proceedings. Tenth International 12 Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding Conference on Parallel and Distributed Systems, 2004. ICPADS 2004. 153–160. https://doi.org/10.1109/ICPADS.2004.1316091

    work page Pith review arXiv 2004

  7. [6]

    Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Tom Leighton, Zhiy- ong Liu, and Jon Kleinberg. 2001. Universal-stability results and performance bounds for greedy contention-resolution protocols. J. ACM 48, 1 (Jan. 2001), 39–69

    work page 2001

  8. [7]

    Rita Azzi, Rima Kilany Chamoun, and Maria Sokhn. 2019. The power of a blockchain-based supply chain. Computers & industrial engineering 135 (2019), 582–592

    work page 2019

Show all 28 references
  1. [8]

    Michael A Bender, Martin Farach-Colton, Simai He, Bradley C Kuszmaul, and Charles E Leiserson. 2005. Adversarial contention resolution for simple channels. In Proc. of the 17th ACM SPAA’05. 325–332

    2005

  2. [9]

    Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P Williamson. 2001. Adversarial queuing theory. Journal of the ACM (JACM) 48, 1 (2001), 13–38

    2001

  3. [10]

    Costas Busch, Bogdan S Chlebus, Dariusz R Kowalski, and Pavan Poudel. 2023. Stable Scheduling in Transactional Memory. In Algorithms and Complexity: 13th International Conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023, Proceed- ings. Springer, 172–186

    2023

  4. [11]

    Costas Busch, Maurice Herlihy, Miroslav Popovic, and Gokarna Sharma. 2022. Dynamic scheduling in distributed transactional memory. Distributed Computing 35, 1 (2022), 19–36

    2022

  5. [12]

    Miguel Castro, Barbara Liskov, et al. 1999. Practical byzantine fault tolerance. In OsDI, Vol. 99. 173–186

    1999

  6. [13]

    Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. 2009. Maximum throughput of multiple access channels in adversarial environments. Distributed Comp. 22 (2009), 93–116

    2009

  7. [14]

    Bogdan S Chlebus, Dariusz R Kowalski, and Mariusz A Rokicki. 2012. Adversarial queuing on the multiple access channel. ACM Transactions on Algorithms (TALG) 8, 1 (2012), 1–31

    2012

  8. [15]

    Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the presence of partial synchrony. Journal of the ACM (JACM) 35, 2 (1988), 288–323

    1988

  9. [17]

    Jelle Hellings and Mohammad Sadoghi. 2021. Byshard: Sharding in a byzantine environment. Proceedings of the VLDB Endowment 14, 11 (2021), 2230–2243

    2021

  10. [18]

    Jelle Hellings and Mohammad Sadoghi. 2022. The Fault-Tolerant Cluster-Sending Problem. In Foundations of Information and Knowledge Systems , Ivan Varzinczak (Ed.). Springer International Publishing, Cham, 168–186

    2022

  11. [19]

    Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. 2016. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 17–30

    2016

  12. [20]

    Thomas McGhin, Kim-Kwang Raymond Choo, Charles Zhechao Liu, and De- biao He. 2019. Blockchain in healthcare applications: Research challenges and opportunities. Journal of network and computer applications 135 (2019), 62–75

    2019

  13. [21]

    Truc Nguyen and My T Thai. 2022. Denial-of-service vulnerability of hash-based transaction sharding: attack and countermeasure. IEEE Trans. Comp. 72, 3 (2022), 641–652

    2022

  14. [22]

    Mayank Raikwar and Danilo Gligoroski. 2021. DoS attacks on blockchain ecosys- tem. In European Conference on Parallel Processing . Springer, 230–242

    2021

  15. [23]

    Adi Rosén. 2002. A note on models for non-probabilistic analysis of packet switching networks. Inform. Process. Lett. 84, 5 (2002), 237–240

    2002

  16. [24]

    Lakshmi Siva Sankar, M Sindhu, and M Sethumadhavan. 2017. Survey of consen- sus protocols on blockchain applications. In Proc. of the 4th ICACCS’17 . 1–5

    2017

  17. [25]

    A Secure. 2018. The zilliqa project: A secure, scalable blockchain platform. (2018)

    2018

  18. [26]

    Gokarna Sharma and Costas Busch. 2014. Distributed transactional memory for general networks. Distributed computing 27, 5 (2014), 329–362

    2014

  19. [27]

    Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. Rapidchain: Scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC . 931–948

    2018

  20. [28]

    Àlvarez, M

    C. Àlvarez, M. Blesa, J. Díaz, M. Serna, and A. Fernández. 2005. Adversarial models for priority-based networks. Networks 45, 1 (2005), 23–35. 13

    2005

Pith tools

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