How to linearize your cluster

The exploration of linearization algorithms for transaction clusters in blockchain networks sheds light on the efficiency and effectiveness of different methodologies under varied conditions. This analysis encompasses several types of data sets to benchmark the performance of three primary algorithms: the Candidate-Set Search (CSS), Spanning-Forest Linearization (SFL), and the Parametric Min-Cut Breakpoints algorithm from the 1989 GGT paper (GGT). The benchmarks are applied across clusters with transaction counts ranging from 26 to 64, reflecting a focus on substantial but manageable cluster sizes for processing.

The simulated 2023 mempools, generated by replaying public network activity into a modified version of Bitcoin Core, produced over 199,076 clusters within the targeted transaction size range. This simulation aimed to provide insights into potential future network behaviors, notably under constraints like the enforced maximum cluster size of 64 transactions. In this context, SFL emerged as the most performant algorithm in terms of average and maximum runtimes, despite CSS showing better lower bounds but faltering significantly in worst-case scenarios.

Further investigations utilized randomly-generated spanning-tree clusters, medium-density clusters, and complete bipartite clusters to assess algorithm performance across different structural complexities. Each dataset presented unique challenges, such as varying numbers of dependencies per transaction, which influenced the algorithms' execution times. Notably, SFL was consistently the best performer in spanning-tree and bipartite setups but showed weaknesses in handling medium-density clusters, especially in worst-case scenarios. These findings suggest that the scalability and efficiency of linearization algorithms can significantly depend on the specific characteristics of transaction clusters.

The methodology employed for benchmarking involved generating numerous random seeds for each algorithm and computing the median runtime across multiple iterations to minimize variance from external factors. This thorough approach underscores the importance of considering both average performance and variability when evaluating algorithmic solutions for blockchain transaction linearization.

All detailed results and graphical representations of the data can be found on the provided GitHub gist, offering a comprehensive resource for further analysis and comparison of these algorithms' capabilities and limitations in optimizing blockchain transaction processing.