delvingbitcoin

Merging incomparable linearizations

Merging incomparable linearizations

Posted on: November 23, 2023 18:01 UTC

Prefix-intersection merging, when applied to linearizations (L_1) and (L_2), results in a new linearization (L_3) which is superior or equal to both (L_1) and (L_2) according to the established preorder on linearizations.

This outcome holds true especially when (L_1) and (L_2) are incomparable, meaning neither is strictly greater than or less than the other in the ordering ((L_1 \ngeq L_2) and (L_1 \nleq L_2)). In such cases, (L_3) not only meets but exceeds the order of (L_1) and (L_2), indicating (L_3 > L_1) and (L_3 > L_2).

This phenomenon was not just theoretically proposed but also empirically tested through extensive computation, involving weeks of CPU time devoted to finding potential counterexamples to this assertion. No counterexamples were found, reinforcing the robustness of prefix-intersection merging as a method for combining linearizations while enhancing their order.

Furthermore, this observation extends beyond prefix-intersection merging to encompass various merge algorithms, including best chunk merging. It underscores an important property: under a total ordering system, the merged linearization (L_3) will always be greater than or equal to the original linearizations (L_1) and (L_2). This reveals the surprising effectiveness of prefix-intersection merging and similar algorithms in achieving a higher order through the process of linearization combination, under the guiding principles of preorder.