Toward Online Sharding in One-Sided Feedback Scenario

Sharding is a promising solution for improving blockchain scalability by distributing the workload across smaller groups of nodes called shards. However, it presents significant challenges, such as balancing tradeoffs between transactions per second (TPS), cross-shard transactions (CSTx), and confirmation latency in dynamic, online environments. While increasing the number of shards enhances TPS within individual shards, it also raises CSTx frequency, leading to higher failure probabilities, increased communication overhead, and prolonged confirmation times. Moreover, managing the number of shards and their configurations under one-sided feedback scenarios adds further complexity. To address these challenges, we model sharding as an online one-sided feedback optimization problem, focusing on maximizing long-term utilities. We introduce a polynomial-time online algorithm that adapts selection probabilities based on feedback information to address this NP-hard problem. Through rigorous analysis, we demonstrate that our approach achieves dynamic regret that grows sub-linearly over time. Extensive evaluations on real-world datasets confirm that our method outperforms existing baseline algorithms in terms of practical performance.