On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding

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.