20.12 Control algorithm using interval operations

This section sketches a control algorithm for replicating the interval-operation states described in 20.11 State machine based on interval operations. Each site has a persistent full database state and may have transient sessions with peers. A session is built on exactly-once, in-order message delivery, typically using TCP while the session remains established.

Persistent site state

A site persistently records the full database state \[ H=State(v_{\mathrm{all}})=\sum[v_{\emptyset},v_{\mathrm{all}}). \] The vector time v_all records every generated atomic operation incorporated by the site. Local generation and receipt of remote intervals advance this persistent state transactionally.

Transient session state

For each peer session, the sender maintains a transient vector time \(\widehat v_{\mathrm{remote}}\). It is the sender's projection of the state the peer will have after processing every interval already queued on the exactly-once, in-order session. It may underestimate changes independently incorporated by the peer and not yet advertised to the sender.

When a session begins, the peers exchange their persistent v_all values. A received advertisement advances the projection by \[ \widehat v_{\mathrm{remote}} := \widehat v_{\mathrm{remote}}\mathbin{\uparrow}v_{\mathrm{advertised}}. \]

If a session fails, its transient projection and any queued transient construction state are discarded. A replacement session exchanges persistent vector times again before calculating new factors.

Sending an R-factor

The sender takes a stable snapshot of its persistent state with output vector time q: \[ H_q=\sum[v_{\emptyset},q). \] The common vector time available in both the snapshot and the projected peer state is \[ c=q\mathbin{\downarrow}\widehat v_{\mathrm{remote}}. \] The sender queues \[ \Delta=Rf(H_q,c)=\sum[c,q) \] on the session. It then advances its projected peer vector time to \[ \widehat v_{\mathrm{remote}} := \widehat v_{\mathrm{remote}}\mathbin{\uparrow}q. \]

The join retains operations advertised by the peer but not yet present at the sender. Because the session delivers queued intervals exactly once and in order, subsequent factors may be calculated against this projected state without waiting for a separate acknowledgement after every message.

Receiving an R-factor

Suppose the receiver's persistent state is \[ H_r=\sum[v_{\emptyset},v_r) \] when it receives \(\Delta=\sum[c,q)\). Earlier messages in the session have already established the history represented by c. The receiver transactionally updates its persistent state by \[ \begin{aligned} H_r &:=H_r\mathbin{\oplus}\Delta\\ &=\sum[v_{\emptyset},v_r\mathbin{\uparrow}q). \end{aligned} \] The merge is safe if the receiver has independently advanced beyond the sender's projection. Any overlap is removed by the interval merge semantics.

Catch-up and steady state

The first interval sent on a session may be large. It can bring a peer up to date after a long disconnection: \[ \Delta_0 = \sum[ q_0\mathbin{\downarrow}\widehat v_{\mathrm{remote}}, q_0 ). \]

After catch-up, the session normally sends small successive factors as the local state advances: \[ \sum[q_0,q_1), \quad \sum[q_1,q_2), \quad \sum[q_2,q_3), \quad\ldots \] They may be produced at interactive rates, such as assignments to the position of a geometrical object while a mouse moves or insertion and deletion of characters while a user types.

The boundaries need not correspond one-to-one with user actions. A sender may batch several changes into a larger interval or send smaller intervals to reduce latency. A type-specific composite representation may also compress many atomic changes into a small message.

Read-only MVCC snapshots

An R-factor need not be constructed from the current mutable head of the database. A sender may work against a read-only MVCC snapshot \[ H_q=\sum[v_{\emptyset},q) \] even when the live database has advanced beyond q. The snapshot can still contain changes absent from the peer and therefore provides a useful factor \(\sum[c,q)\). Later snapshots send the remaining intervals.

The endpoint carried by the transmitted factor must be q, the vector time of the snapshot. The sender must not advance the projected peer state to the newer live v_all unless the corresponding interval has actually been queued.

An MVCC snapshot may include immutable, read-only information about the fields changed in the history represented by the snapshot. Conceptually it can answer \[ ChangedFields(c,q), \] returning fields that may contribute to \(\sum[c,q)\). The sender need only inspect those fields in the snapshot rather than scan the entire database.

Change indexes

One possible change index associates atomic-operation identities with affected fields: \[ (s,t)\longmapsto\{\text{fields affected by }op(s,t)\}. \] It gives \[ ChangedFields(c,q) = \bigcup_{s\in S}\ \bigcup_{c(s)\le t<q(s)} ChangedFields(s,t). \] Other implementations may use commit manifests, per-field causal summaries, indexes over ranges of sequence numbers, or compacted checkpoints.

The result may conservatively contain false positives. A field's concrete composite representation can determine that its R-factor is empty. False negatives are unsafe: after claiming that the peer will reach q, the session must have queued every field contribution to \(\sum[c,q)\). Changes to causal or conflict-resolution metadata count even when the visible field value remains unchanged.

Transient dirty sets

For steady-state replication, a session may additionally maintain a transient set of fields that have changed. A mutator committing a field change can notify active sessions, or append the field identifier to a shared change journal from which sessions maintain their own cursors. Repeated changes to a field coalesce in a set.

The persistent snapshot information remains authoritative. A dirty set is an acceleration structure that identifies fields worth inspecting; it does not define the interval semantics. This distinction also allows a new session to construct its initial catch-up factor even though it did not observe earlier notifications.

If dirty entries are cleared after transmission, each entry must carry a generation or commit position. Suppose a sender reads field f from snapshot q and f changes again while the message is being constructed. The sender may remove f only if its recorded dirty generation has not advanced. Otherwise f must remain dirty for a later snapshot. This prevents a stale snapshot from clearing a newer unsent change.

Implementation boundary

The semantic protocol requires a persistent full state, a projected peer vector time and transmission of the appropriate R-factor. MVCC layouts, change indexes, dirty sets, journals, iterators, batching, encoding and flow control are implementation choices. They may cooperate to produce an R-factor efficiently, but the queued message must represent the complete interval claimed by its endpoints.