  Sharding is a promising technique for addressing the scalability issues of
blockchain. It divides the $n$ participating nodes into $s$ disjoint groups
called shards, where each shard processes transactions in parallel. We
investigate scheduling algorithms for the blockchain sharding systems, where
each transaction resides in a shard of the communication graph and attempts to
access accounts at possibly remote shards. We examine batch scheduling problems
on the shard graph $G_s$, where given a set of transactions, we aim to find
efficient schedules to execute them as fast as possible. First, we present a
centralized scheduler where one of the shards has global knowledge of
transactions to be processed. For general graphs, where the transaction and its
accessing objects are arbitrarily far from each other with a maximum distance
$d$, the centralized scheduler provides $O(kd)$ approximation to the optimal
schedule, where $k$ is the maximum number of shards each transaction accesses.
Consequently, for a Clique graph where shards are at a unit distance from each
other, we obtain $O(k)$ approximation to the optimal schedule. We also get $O(k
\log s)$ approximation for Hypercube, Butterfly, and $g$-dimensional Grid,
where $g=O(\log s)$. Next, we provide a centralized scheduler with a bucketing
approach that offers improved bounds for special cases. Finally, we provide a
distributed scheduler where shards do not require global transaction
information. We achieve this by using a hierarchical clustering of the shards
and using the centralized scheduler in each cluster. We show that the
distributed scheduler has a competitive ratio of $O(\mathcal{A_\mathcal{CS}}
\log ^2 s)$, where $\mathcal{A_\mathcal{CS}}$ is the approximation ratio of the
centralized scheduler. To our knowledge, we are the first to give provably fast
transaction scheduling algorithms for blockchain sharding systems.
