On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding
ACM Transactions on Parallel Computing · 06.11.2026
DOI: 10.1145/3857391 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, online erschienen am 06.11.2026. Verfasst von Ramesh Adhikari und 2 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben.
Abstract (Originalsprache)
We consider blockchain sharding where n processing nodes are divided into s disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph G s where transactions arrive online over time and are not known in advance. Each transaction may access at most k shards, and we denote by d the worst distance between a transaction and its accessing shards. To handle different values of d , we assume a locality sensitive decomposition of G s into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model , where leaders are not aware of the current state of the transaction accounts, and we prove a \(O(d \log ^2 s \cdot \min \lbrace k, \sqrt {s}\rbrace) \) competitive ratio for latency. We then consider the stateful model , where leader shards gather the current state of accounts, and we prove a \(O(\log s\cdot \min \lbrace k, \sqrt {s}\rbrace +\log ^2 s) \) competitive ratio for latency. We show that for any ϵ > 0, approximating the optimal schedule within a \((\min \lbrace k, \sqrt {s}\rbrace)^{1 -\epsilon } \) factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. We also provide the simulation results of the proposed scheduling algorithms.
Zitieren
APA
Adhikari, R., Busch, C., & Popovic, M. (2026). On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding. ACM Transactions on Parallel Computing. https://doi.org/10.1145/3857391
Vancouver
Adhikari R, Busch C, Popovic M. On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding. ACM Transactions on Parallel Computing. 2026. doi:10.1145/3857391
BibTeX
@article{Adhikari2026,
author = {Adhikari, Ramesh and Busch, Costas and Popovic, Miroslav},
title = {On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding},
journal = {ACM Transactions on Parallel Computing},
year = {2026},
doi = {10.1145/3857391}
}
EUVIMED