Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

LWW Property Resolution During Concurrent Updates

The Problem

Two users concurrently edit the same entity. User A sets title = "Alpha" on one replica; User B sets title = "Beta" on another. Both writes happen independently – neither knows about the other. When the replicas sync, the system must pick one winner for title and guarantee that every replica picks the same one, no matter which write it saw first.

LWW (Last-Writer-Wins) resolution answers this question with two rules applied in order:

  1. Causal dominance. If one write causally follows another (the writer had already seen the earlier value), the later write wins.
  2. Deterministic tiebreak. If neither write has seen the other (they are truly concurrent), the write with the lexicographically greater EventId wins. Since EventIds are SHA-256 hashes, this is an arbitrary but consistent total order that every replica can compute independently.

The Three-Stage Pipeline

When the event DAG detects that branches have diverged, the merge proceeds in three conceptual stages:

1. Layer computation

All events between the meet point (the last common ancestor of the two branches) and the branch tips are partitioned into concurrency layers – groups of events at the same causal depth. Within a layer, events are either already applied (the replica has already incorporated them) or to-apply (new to this replica). Layers are produced in topological order so that earlier causal history is resolved before later history. See Event Layers for the precise definition of a layer and the guarantees it provides.

2. Per-layer resolution

For each layer, every LWW property is resolved independently. The algorithm starts with the property’s current stored value as the incumbent, then considers every event in the layer – both already-applied and to-apply – as challengers. The resolution rules below determine whether a challenger displaces the incumbent.

3. State mutation

Only winners that originate from to-apply events actually mutate the backend. If the winning write was already in the replica’s state (from an already-applied event or from the stored seed), nothing changes. After all mutations, subscribers are notified for each changed property.

Resolution Rules

When a challenger event competes against the current incumbent for a property, three rules are applied in priority order:

  1. Older-than-meet rule. If the incumbent value was written by an event that predates the meet point, the challenger wins unconditionally. Rationale: every event in the layer descends from the meet, which itself descends from (or equals) the old event. The challenger is strictly newer.

  2. Causal dominance. If one event is an ancestor of the other in the accumulated DAG, the descendant wins. This respects user intent: a write made after seeing a prior value should supersede it.

  3. Lexicographic tiebreak. If the two events are truly concurrent (neither descends from the other), the one with the greater EventId wins. This is an arbitrary but deterministic rule that ensures every replica reaches the same conclusion.

If no incumbent exists for a property, the first event to write it wins by default.

Per-Property Independence

Each property is resolved independently. In a diamond DAG:

      A (genesis, title="Init", artist="Init")
     / \
    B    C

Event B writes title = "B-title". Event C writes artist = "C-artist".

  • title: Only B touched it. B’s value wins.
  • artist: Only C touched it. C’s value wins.

Final state: title = "B-title", artist = "C-artist". When both branches write the same property, the resolution rules above determine the winner. Different properties may have different winning events from the same layer.

Determinism

The system guarantees that the same set of concurrent events always resolves to the same property values, regardless of event delivery order.

Worked example

Replicas R1 and R2 both hold an entity at head [G] (genesis). Three concurrent events A, B, C – all parented on [G] – arrive in different orders. Assume EventId(A) < EventId(B) < EventId(C).

R1 receives A, then B, then C:

StepArrivesLayer (already / to-apply)Winner for each property
1A– (direct apply)A’s values
2Balready=[A], to-apply=[B]max(A, B) = B by tiebreak
3Calready=[A, B], to-apply=[C]max(B, C) = C by tiebreak

R2 receives C, then A, then B:

StepArrivesLayer (already / to-apply)Winner for each property
1C– (direct apply)C’s values
2Aalready=[C], to-apply=[A]max(C, A) = C by tiebreak
3Balready=[A, C], to-apply=[B]max(C, B) = C by tiebreak

Both replicas converge to the same head [A, B, C] and the same winner (C) for every property that all three events wrote. The key insight: pairwise max() over EventIds is commutative and associative, so the evaluation order does not matter.

The ingredients of determinism

  1. Lexicographic tiebreak is a total order. EventIds are SHA-256 hashes of (entity_id, operations, parent_clock). The byte-level ordering is consistent across all replicas.

  2. max() is commutative and associative. Pairwise competition produces the same result regardless of evaluation order.

  3. Causal dominance is objective. The DAG structure is the same on every replica, so ancestor/descendant queries return the same answers everywhere.

  4. The older-than-meet rule is deterministic. Whether a stored event falls inside or outside the accumulated DAG depends only on the DAG contents, which converge across replicas.

  5. Stored state tracks winners. Each layer updates the stored event_id for mutated properties, so subsequent layers seed from the correct incumbent.

Prerequisite: causal application order

Determinism relies on events being applied parents-first: if event D has parent [C], a replica must integrate C before D. This is an application-order invariant, not a transport guarantee – the receiver enforces it itself by staging each multi-event batch and topologically sorting it by in-batch parent edges (event_dag/ordering.rs) before applying. Sender order is never trusted.

Integration With Entity::apply_event

The DivergedSince handler in Entity::apply_event ties the pipeline together:

  1. Decompose the comparison result into the causal relation and the accumulated DAG.
  2. Build the layer iterator from the meet point and current head.
  3. Collect all layers (async; may hit storage).
  4. Acquire the entity write lock; re-check the head for TOCTOU safety.
  5. For each layer in topological order, call the resolution algorithm on every property backend. If a to-apply event introduces a new backend type, create it and replay earlier layers first.
  6. Update the head, release the lock, and broadcast change notifications.

Test Coverage

See Testing Strategy for the full test matrix. Key test files:

  • tests/tests/lww_resolution.rs – deeper-branch-wins, sequential last write, lexicographic tiebreak, per-property independence, order independence.
  • tests/tests/determinism.rs – two-event same-property determinism (the most critical test: two nodes apply events in opposite order and assert identical final state), deep diamond, multi-property convergence, three-way fork.