EUVIMEDEUVIMED entdecken
Crossref

On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding

Ramesh Adhikari, Costas Busch, Miroslav Popovic

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →