Spanning-forest cluster linearization

The issue under discussion revolves around the Shared Fragment Log (SFL) and its susceptibility to enter repeating cycles even when splits are restricted to a maximum degree, q. A particular instance demonstrates this phenomenon through a complex 15-transaction cluster with 30 dependencies, where it's possible to undergo a series of 24 splits and merges that paradoxically loop back to the original state. This cycle is initiated from a predefined spanning tree composed of various transactions linked through dependencies. The process involves sequentially deactivating one dependency while activating another, which may include previously inactive (grey) ones. These steps are meticulously outlined, showcasing the transitions between states facilitated by the manipulation of transaction dependencies.

The discovery of such a cycle was made possible through an innovative approach that involved constructing a graph representing the states of SFL. Each node within this graph symbolizes a unique set of active dependencies, while the edges denote potential actions (splits and self-merges) that SFL can execute. This exploration strategy, which was first proposed by @ajtowns and later implemented with significant computational resources by @gmaxwell, revealed the critical insight that SFL lacks a termination guarantee. This finding challenges the assumption of guaranteed progress within the system over time.

Despite the theoretical possibility of these repeating cycles, their practical impact might be somewhat mitigated by the inherent randomness in the system. It has been observed that even in clusters prone to such cycles, there exists a significant chance—ranging from 50% to 80%—of exiting these loops at each step due to randomization. Nevertheless, the primary concern remains with clusters that present inescapable repeating states, posing a fundamental challenge to the reliability of SFL under specific conditions. This analysis underscores the importance of recognizing and addressing the limitations inherent in the design and implementation of complex systems like SFL.