  Sharding is used to improve the scalability and performance of blockchain
systems. We investigate the stability of blockchain sharding, where
transactions are continuously generated by an adversarial model. The system
consists of $n$ processing nodes that are divided into $s$ shards. Following
the paradigm of classical adversarial queuing theory, transactions are
continuously received at injection rate $\rho \leq 1$ and burstiness $b > 0$.
We give an absolute upper bound $\max\{ \frac{2}{k+1}, \frac{2}{
\left\lfloor\sqrt{2s}\right\rfloor}\}$ on the maximum injection rate for which
any scheduler could guarantee bounded queues and latency of transactions, where
$k$ is the number of shards that each transaction accesses. We next give a
basic distributed scheduling algorithm for uniform systems where shards are
equally close to each other. To guarantee stability, the injection rate is
limited to $\rho \leq \max\{ \frac{1}{18k}, \frac{1}{\lceil 18 \sqrt{s} \rceil}
\}$. We then provide a fully distributed scheduling algorithm for non-uniform
systems where shards are arbitrarily far from each other. By using a
hierarchical clustering of the shards, stability is guaranteed with injection
rate $\rho \leq \frac{1}{c_1d \log^2 s} \cdot \max\{ \frac{1}{k},
\frac{1}{\sqrt{s}} \}$, where $d$ is the worst distance of any transaction to
the shards it will access, and $c_1$ is some positive constant. We also conduct
simulations to evaluate the algorithms and measure the average queue sizes and
latency throughout the system. To our knowledge, this is the first adversarial
stability analysis of sharded blockchain systems.
