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 ρ ≤ 1 and burstiness b > 0. We give an absolute upper bound max{2/k+1, 2⌊√2s⌋} 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 ρ ≤ max{1/18k, 1/ ⌈18√s⌉}. 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 ρ ≤ 1/(c1d log2 s) ⋅ max{1/k, 1/√s}, where d is the worst distance of any transaction to the shards it will access, and c1 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.
Sharding is a promising technique for addressing the scalability issues of blockchain, and this technique is especially important for IoT, edge, or mobile computing. It divides the \(n\) participating nodes into \(s\) disjoint groups called shards, where each shard processes transactions in parallel. We examine batch scheduling problems on the shard graph \(G_s\), where we find efficient schedules for a set of transactions. First, we present a centralized scheduler where one of the shards is considered as a leader, who receives the transaction information from all of the other shards and determines the schedule to process the transactions. For general graphs, where a 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. Next, we provide a centralized scheduler with a bucketing approach that offers improved bounds for the case where \(G_s\) is a line graph, or the \(k\) objects are randomly selected. 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}} \cdot \log d \cdot \log 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. We also present simulation results for our schedulers and compare their performance with a lock-based approach. The results show that our schedulers are generally better with up to 3x lower latency and 2x higher throughput.
19 November 2025 in Distributed Ledger Technologies: Research and Practice
Blockchain is known for its promising features, such as decentralization, fault tolerance, transparency, and immutability. Thus, it has been used in many industries and applications, including cryptocurrency, finance, smart cities, healthcare, and manufacturing. However, blockchain suffers from scalability issues and provides low transaction throughput and high latency. Sharding is used to solve these scalability and performance issues by dividing the blockchain network into smaller clusters of nodes called shards, and each shard processes transactions in parallel. However, the sharding protocol is still in its early stages and encounters multiple challenges. In this paper, we survey cutting-edge blockchain sharding papers, mainly focusing on transaction processing aspects such as intra-shard transaction processing, cross-shard communication, and cross-shard transaction processing. We also examine security vulnerabilities and attack vectors associated with sharded blockchain systems . We review existing techniques, highlight key challenges and problems, and suggest potential future research directions.