Fast Transaction Scheduling in Blockchain Sharding

分片是解决区块链可扩展性问题的一种有前途的技术。它将$n$个参与节点划分为$s$个不相交的分片，每个分片并行处理交易。我们研究了区块链分片系统的调度算法，其中每个交易都驻留在通信图的一个分片中，并尝试访问可能远离其所在分片的账户。我们研究了分片图$G_s$上的批处理调度问题，其中给定一组交易，我们旨在找到尽可能快地执行它们的有效时间表。首先，我们提出了一种集中式调度程序，其中一个分片具有处理交易的全局知识。对于一般的图形，其中交易及其访问对象彼此远离且最大距离为$d$，集中式调度程序提供$O(kd)$近似于最优时间表，其中$k$是每个交易访问的最大分片数。因此，对于一个完全图，其中分片之间距离为1，我们获得$O(k)$近似于最优时间表。对于超立方体、蝴蝶图和$g$维网格，其中$g=O(\log s)$，我们也获得了$O(k\log s)$的近似值。接下来，我们提供了一种带有桶式方法的集中式调度程序，为特殊情况提供了改进的界限。最后，我们提供了一种分布式调度程序，其中分片不需要全局交易信息。我们通过使用分片的分层聚类和在每个聚类中使用集中式调度程序来实现这一点。我们证明，分布式调度程序具有$O(\mathcal{A_\mathcal{CS}}\log^2 s)$的竞争比率，其中$\mathcal{A_\mathcal{CS}}$是集中式调度程序的近似比率。据我们所知，我们是第一个为区块链分片系统提供可证明快速的交易调度算法的人。

论文旨在解决区块链分片系统中交易调度问题，提出了集中式调度器和分布式调度器两种方案，并进行了理论分析。

论文提出了集中式调度器和分布式调度器两种方案，其中集中式调度器可以在图的直径为d的情况下提供O(kd)或O(klog(s))的近似最优调度，而分布式调度器则采用分层聚类的方式，每个聚类使用集中式调度器，并证明了其竞争比为O(AC_S * log^2(s))。

论文提出的算法是针对区块链分片系统中交易调度问题的，具有一定的理论分析和证明，其中集中式调度器和分布式调度器两种方案都有不错的性能表现。实验部分使用了人工生成的数据集进行验证，并进行了对比实验。值得进一步研究的是如何将算法应用到实际的区块链系统中。

近期的相关研究包括：1. Scalable Byzantine consensus via hardware-assisted secret sharing. 2. Blockchain sharding: A comprehensive survey. 3. A survey on blockchain consensus mechanisms. 4. A brief survey of blockchain consensus algorithms。