Spanning-forest cluster linearization

In recent updates to the merge and split selection mechanisms, significant improvements have been achieved in processing efficiency and security against manipulation. The method for choosing which dependency to activate between two merging chunks has been refined. Previously, a dependency was selected based on a randomized but not uniformly random approach, favoring dependencies from the initial transaction within a cluster. This method has evolved to a strategy where a uniformly random dependency is selected, a change that not only simplifies the process by eliminating the need for maintaining randomly sorted lists of dependencies per transaction but also markedly enhances worst-case performance in densely populated synthetic clusters, with improvements up to a factor of 1.5x noted. Moreover, this adjustment diminishes the likelihood of adversaries successfully influencing decision-making processes.

Another noteworthy modification concerns how failures in chunk splits are handled. Specifically, tracking the number of consecutive unsuccessful split attempts on a chunk has been implemented. When the count is just one less than a multiple of three, a different approach is taken: instead of splitting based on the dependency with the highest $q$ value, a uniformly random dependency among those with positive $q$ values within the chunk is chosen for the split. This method introduces an element of randomness that, while generally showing max-$q$ to perform well across various graph types, mitigates potential vulnerabilities to manipulation by adversarially constructed clusters. This randomized step is triggered relatively infrequently, only after every third failed attempt, thereby minimizing its impact on performance in realistic scenarios where splits typically succeed without issue.

The efficacy of these adjustments has been substantiated through updated benchmarks, discussed in detail in a separate thread. These developments underscore a continued confidence in the SFL (Split-Find-Linearize) approach for managing clusters, suggesting it remains a robust and efficient strategy for cluster linearization.