cluster_linearize::SpanningForestState

template<
    typename SetType,
    typename CostModel = SFLDefaultCostModel>
class SpanningForestState;

Description

At all times, each dependency is marked as either "active" or "inactive". The subset of active dependencies is the state of the SFL algorithm. The implementation maintains several other values to speed up operations, but everything is ultimately a function of what that subset of active dependencies is.

Given such a subset, define a chunk as the set of transactions that are connected through active dependencies (ignoring their parent/child direction). Thus, every state implies a particular partitioning of the graph into chunks (including potential singletons). In the extreme, each transaction may be in its own chunk, or in the other extreme all transactions may form a single chunk. A chunk's feerate is its total fee divided by its total size.

The algorithm consists of switching dependencies between active and inactive. The final linearization that is produced at the end consists of these chunks, sorted from high to low feerate, each individually sorted in an arbitrary but topological (= no child before parent) way.

We define four quality properties the state can have:

• acyclic: The state is acyclic whenever no cycle of active dependencies exists within the graph, ignoring the parent/child direction. This is equivalent to saying that within each chunk the set of active dependencies form a tree, and thus the overall set of active dependencies in the graph form a spanning forest, giving the algorithm its name. Being acyclic is also equivalent to every chunk of N transactions having exactly N-1 active dependencies.

For example in a diamond graph, D->{B,C}->A, the 4 dependencies cannot be simultaneously active. If at least one is inactive, the state is acyclic.

The algorithm maintains an acyclic state at all times as an invariant. This implies that activating a dependency always corresponds to merging two chunks, and that deactivating one always corresponds to splitting two chunks.

• topological: We say the state is topological whenever it is acyclic and no inactive dependency exists between two distinct chunks such that the child chunk has higher or equal feerate than the parent chunk.

The relevance is that whenever the state is topological, the produced output linearization will be topological too (i.e., not have children before parents). Note that the "or equal" part of the definition matters: if not, one can end up in a situation with mutually-dependent equal-feerate chunks that cannot be linearized. For example C->{A,B} and D->{A,B}, with C->A and D->B active. The AC chunk depends on DB through C->B, and the BD chunk depends on AC through D->A. Merging them into a single ABCD chunk fixes this.

The algorithm attempts to keep the state topological as much as possible, so it can be interrupted to produce an output whenever, but will sometimes need to temporarily deviate from it when improving the state.

• optimal: For every active dependency, define its top and bottom set as the set of transactions in the chunks that would result if the dependency were deactivated; the top being the one with the dependency's parent, and the bottom being the one with the child. Note that due to acyclicity, every deactivation splits a chunk exactly in two.

We say the state is optimal whenever it is topological and it has no active dependency whose top feerate is strictly higher than its bottom feerate. The relevance is that it can be proven that whenever the state is optimal, the produced linearization will also be optimal (in the convexified feerate diagram sense). It can also be proven that for every graph at least one optimal state exists.

Note that it is possible for the SFL state to not be optimal, but the produced linearization to still be optimal. This happens when the chunks of a state are identical to those of an optimal state, but the exact set of active dependencies within a chunk differ in such a way that the state optimality condition is not satisfied. Thus, the state being optimal is more a "the eventual output is known to be optimal".

• minimal: We say the state is minimal when it is:

• acyclic

• topological, except that inactive dependencies between equal-feerate chunks are allowed as long as they do not form a loop.

• like optimal, no active dependencies whose top feerate is strictly higher than the bottom feerate are allowed.

• no chunk contains a proper non-empty subset which includes all its own in-chunk dependencies of the same feerate as the chunk itself.

A minimal state effectively corresponds to an optimal state, where every chunk has been split into its minimal equal-feerate components.

The algorithm terminates whenever a minimal state is reached.

This leads to the following high-level algorithm:

• Start with all dependencies inactive, and thus all transactions in their own chunk. This is definitely acyclic.

• Activate dependencies (merging chunks) until the state is topological.

• Loop until optimal (no dependencies with higher-feerate top than bottom), or time runs out:

• Deactivate a violating dependency, potentially making the state non-topological.

• Activate other dependencies to make the state topological again.

• If there is time left and the state is optimal:

• Attempt to split chunks into equal-feerate parts without mutual dependencies between them. When this succeeds, recurse into them.

• If no such chunks can be found, the state is minimal.

• Output the chunks from high to low feerate, each internally sorted topologically.

When merging, we always either:

• Merge upwards: merge a chunk with the lowest-feerate other chunk it depends on, among those with lower or equal feerate than itself.

• Merge downwards: merge a chunk with the highest-feerate other chunk that depends on it, among those with higher or equal feerate than itself.

Using these strategies in the improvement loop above guarantees that the output linearization after a deactivate + merge step is never worse or incomparable (in the convexified feerate diagram sense) than the output linearization that would be produced before the step. With that, we can refine the high-level algorithm to:

• Start with all dependencies inactive.

• Perform merges as described until none are possible anymore, making the state topological.

• Loop until optimal or time runs out:

• Pick a dependency D to deactivate among those with higher feerate top than bottom.

• Deactivate D, causing the chunk it is in to split into top T and bottom B.

• Do an upwards merge of T, if possible. If so, repeat the same with the merged result.

• Do a downwards merge of B, if possible. If so, repeat the same with the merged result.

• Split chunks further to obtain a minimal state, see below.

• Output the chunks from high to low feerate, each internally sorted topologically.

Instead of performing merges arbitrarily to make the initial state topological, it is possible to do so guided by an existing linearization. This has the advantage that the state's would-be output linearization is immediately as good as the existing linearization it was based on:

• Start with all dependencies inactive.

• For each transaction t in the existing linearization:

• Find the chunk C that transaction is in (which will be singleton).

• Do an upwards merge of C, if possible. If so, repeat the same with the merged result. No downwards merges are needed in this case.

After reaching an optimal state, it can be transformed into a minimal state by attempting to split chunks further into equal-feerate parts. To do so, pick a specific transaction in each chunk (the pivot), and rerun the above split-then-merge procedure again:

• first, while pretending the pivot transaction has an infinitesimally higher (or lower) fee than it really has. If a split exists with the pivot in the top part (or bottom part), this will find it.

• if that fails to split, repeat while pretending the pivot transaction has an infinitesimally lower (or higher) fee. If a split exists with the pivot in the bottom part (or top part), this will find it.

• if either succeeds, repeat the procedure for the newly found chunks to split them further. If not, the chunk is already minimal. If the chunk can be split into equal-feerate parts, then the pivot must exist in either the top or bottom part of that potential split. By trying both with the same pivot, if a split exists, it will be found.

What remains to be specified are a number of heuristics:

• How to decide which chunks to merge:

• The merge upwards and downward rules specify that the lowest-feerate respectively highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate candidates, a uniformly random one among them is picked.

• How to decide what dependency to activate (when merging chunks):

• After picking two chunks to be merged (see above), a uniformly random dependency between the two chunks is activated.

• How to decide which chunk to find a dependency to split in:

• A round-robin queue of chunks to improve is maintained. The initial ordering of this queue is uniformly randomly permuted.

• How to decide what dependency to deactivate (when splitting chunks):

• Inside the selected chunk (see above), among the dependencies whose top feerate is strictly higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency is deactivated.

• After every split, it is possible that the top and the bottom chunk merge with each other again in the merge sequence (through a top->bottom dependency, not through the deactivated one, which was bottom->top). Call this a self-merge. If a self-merge does not occur after a split, the resulting linearization is strictly improved (the area under the convexified feerate diagram increases by at least gain/2), while self-merges do not change it.

• How to decide the exact output linearization:

• When there are multiple equal-feerate chunks with no dependencies between them, pick the smallest one first. If there are multiple smallest ones, pick the one that contains the last transaction (according to the provided fallback order) last (note that this is not the same as picking the chunk with the first transaction first).

• Within chunks, pick among all transactions without missing dependencies the one with the highest individual feerate. If there are multiple ones with the same individual feerate, pick the smallest first. If there are multiple with the same fee and size, pick the one that sorts first according to the fallback order first.