Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding
Preprint
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 $ρ$ 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 $ρ\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 $ρ\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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Lockless Blockchain Sharding with Multiversion Control2023
- Denial-of-Service Vulnerability of Hash-based Transaction Sharding: Attack and CountermeasureIEEE Transactions on Computers, 2022
- Dynamic scheduling in distributed transactional memoryDistributed Computing, 2021
- The power of a blockchain-based supply chainComputers & Industrial Engineering, 2019
- Blockchain in healthcare applications: Research challenges and opportunitiesJournal of Network and Computer Applications, 2019
- Distributed transactional memory for general networksDistributed Computing, 2014
- Adversarial models for priority‐based networksNetworks, 2004
- The impact of failure management on the stability of communication networks2004
- A note on models for non-probabilistic analysis of packet switching networksInformation Processing Letters, 2002
- Adversarial queuing theoryJournal of the ACM, 2001