delvingbitcoin

## Cluster mempool definitions & theory

### Posted on: December 10, 2023 15:26 UTC

In the realm of graph theory and its application to transaction processing, a concept known as chunking is explored.

Chunking involves dividing a graph, G, into a series of non-overlapping sets known as chunks. These chunks must satisfy certain conditions: they form a partition covering the entire graph without any overlap; every prefix of these chunks—cumulatively considered up to any point in the sequence—must be a topological subset of G; additionally, the feerates for these sets decrease monotonically.

A theorem pertaining to chunking asserts that there exists a unique corresponding chunking for any given linearization of transactions, regardless of the order in which merge operations are performed. This suggests a consistent way of defining chunking across different scenarios. However, it's proposed that the definition should specify that each prefix of the chunking itself must be topological, rather than the individual prefixes within each chunk. This would align with ensuring the topology only needs to be valid at the borders between chunks.

Another theorem, the Chunk Reordering Theorem, posits that reordering transactions within a single chunk of a linearization will result in an equally optimal or improved arrangement. Nonetheless, there seems to be a need for clarification on whether this theorem should only apply to reorderings that maintain topological validity.

Furthermore, in achieving an optimal linearization or chunking, it is theorized that the resulting chunks ought to comprise connected components with uniform feerate. If not, the chunks could potentially be further subdivided, enhancing the structure. This implies that an optimal chunking is one where no further beneficial splits are possible, and all chunks have reached a state where their internal feerate uniformity cannot be improved by rearrangement.

These theoretical insights into chunking could potentially improve transaction processing efficiency by informing the design of algorithms that optimize the ordering and grouping of transactions based on their feerate and topological dependencies.