Ordering storage generations across counter wrap

The missing contract behind a version field

Our checksum and lost-write analysis requires an independently trusted expected generation. This note examines an additional assumption: what does ordering those generations mean? Copying a signed-subtraction idiom does not establish a safe history window, object identity or a durable reference.

RFC 1982 defines finite serial arithmetic for DNS. Its comparison rule is useful here as a mathematical reference, not as a specification for disk formats. For w-bit values a and b, calculate the forward difference modulo 2^w. Equality has difference zero; a positive difference below half the space places a before b. Exactly half has undefined ordering. [1, sections 3-5]

M = 2 ** bits
d = (b - a) modulo M
d == 0:       equal
0 < d < M/2:  a is before b
d == M/2:     ambiguous
M/2 < d < M:  a is after b

The function classifies two values; it cannot prove how many increments happened between observations. A caller needs that external bound. A checksum over the counter adds integrity, not missing history.

All 65,536 pairs in an 8-bit space

Hesela enumerated every ordered pair from 0 through 255. A separate piecewise implementation checks the modular function; reversing inputs checks symmetry. There is no sampled device population or random seed.

Ordinary unsigned a < b disagrees with the serial before relation for 16,256 of 65,280 defined pairs, including equality in the denominator. These counts describe the complete artificial input space, not the chance of a production fault.

For example, 254 precedes 3 across an 8-bit wrap: the forward distance is five, although 254 is the larger integer. The test also covers 64-bit boundaries using arbitrary-precision integers.

Rejecting half-range ties still does not make a sort order

0 before 100 before 200 before 0

Every pair in this cycle has a defined comparison. Yet choosing the newest value by repeatedly comparing a running winner depends on input order. Across the six permutations of the same three values, each value wins twice. A guard that rejects only exactly-half-range differences cannot catch this.

A common unwrapped interval whose span is strictly below half the sequence space supplies a consistent ordering for values in that interval. Our tests exhaust increasing triples inside every such maximal integer window in a 4-bit space. All 5,376 permutations of those 896 triples select the actual latest value. This is a positive control; the unrestricted 8-bit cycle is the negative control. Neither test proves that a real recovery tool retained enough history.

The same boundary in two storage codebases

Linux v6.16 JBD2 explicitly uses modular transaction-ID comparisons: tid_gt assigns the unsigned difference to an int and tests whether it is positive. [2] PostgreSQL REL_18_0 uses a signed 32-bit difference for normal XIDs; TransactionIdPrecedes tests whether it is negative. Permanent XIDs have a separate unsigned-comparison branch. [3]

We compiled isolated expressions with cc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, on x86-64 Linux, using the same unsigned input width. All inputs below are normal-XID values, at least three. These probes are not linked to PostgreSQL or the kernel. C11 conversion of an out-of-range unsigned value to signed is implementation-defined; the recorded result is scoped to this compiler.

At the half-range input, the before expression says true in both directions while the greater-than expression says false in both directions. This is not evidence of a PostgreSQL or JBD2 defect: we have not shown that their lifecycle rules allow such inputs to coexist. It shows why extracting an internal comparator without its invariants is unsafe. The receipt also contains three 32-bit cycle edges; the expressions accept every edge.

Freezing and epochs preserve different information

PostgreSQL's wraparound protection makes old row versions permanently visible by freezing them, and requires vacuuming before their normal XIDs become too old. Modern versions use a flag rather than simply replacing the stored insertion XID. This is a lifecycle mechanism, not just a clever comparator. [5]

Its 64-bit xid8 includes an epoch, while ordinary xid is 32 bits. Assignment order is not necessarily transaction-start order. [6] The pinned header skips reserved XIDs during advancement and combines epoch and low XID in FullTransactionId; reconstructing a full ID from a low ID is explicitly conditioned on an allowable interval. [4]

In the generated example, (epoch 7, counter 42) and (epoch 8, counter 42) have equal low counters but different full values. Keeping the epoch works only when it belongs to the same trusted identity and history. Restoring both a record and its reference from an old snapshot can erase that distinction; numeric wrap and rollback are separate problems. Compare rollback protection.

A counter is not an incarnation identifier

Birrell and Nelson's 1984 RPC paper makes the distinction concrete: its call identity combines machine, process and sequence, with at most one outstanding call per activity. It separately uses a conversation identifier to distinguish caller incarnations after restart, and a binding identifier to address server restart. Duplicate tracking also depends on the lifetime of retransmitted packets. [7, section 3.2, pp. 50-51]

The storage analogy is ours: ordering within one history does not identify which history a recovered record belongs to. This paper does not specify JBD2 recovery or PostgreSQL freezing. See incarnation identifier.

What to record when interpreting a generation

• Field width, reserved values, increment rules and the exact comparison used by that format.
• The object or journal identity: numbers from different instances need not be comparable.
• A justified retention or observation bound, not merely a small-looking modular difference.
• How epoch information survives restart, restore, failover and metadata loss.
• The response to ambiguous or out-of-window evidence: retain it as unresolved rather than guessing which record is current.

This synthesis connects existing algorithms and documents their conditions; it claims no new comparison algorithm. No database, filesystem recovery, device failure or power loss was exercised. The useful result is a compact counterexample and a reproducible way to test an often omitted assumption in freshness checks.

Reproduce and reuse

Download the model, tests, C probe and capture script into one directory. Python 3 uses only its standard library. Native capture additionally requires a C compiler and access to the three versioned upstream source files.

python3 -m unittest -v test_serial_order.py
python3 serial_order.py
python3 capture_serial_order.py

The exact results and native receipt record scope, source SHA-256 hashes and harness hashes. The receipt checks source markers before compiling isolated expressions; it does not compile the complete upstream functions. Definitions: serial number arithmetic and transaction ID wraparound.

Primary sources

1. Elz and Bush. RFC 1982: Serial Number Arithmetic, sections 3-5 (1996). Accessed 2026-10-18.
2. Linux v6.16 include/linux/jbd2.h: tid_gt and tid_geq. Accessed 2026-10-18.
3. PostgreSQL REL_18_0 transam.c: TransactionIdPrecedes and TransactionIdFollows. Accessed 2026-10-18.
4. PostgreSQL REL_18_0 transam.h: reserved XIDs, advance and FullTransactionId. Accessed 2026-10-18.
5. PostgreSQL 18 documentation: preventing transaction ID wraparound failures. Accessed 2026-10-18.
6. PostgreSQL 18 documentation: transactions and identifiers. Accessed 2026-10-18.
7. Birrell and Nelson. Implementing Remote Procedure Calls, ACM TOCS 2(1), 39-59 (1984), section 3.2. Accessed 2026-10-18.