FAILURE MAP
← Case archive

FA-75286 / CRDT convergence / Open access

Awareness presence table: the local user times out of its own presence table · case 01

The local user disappears from presence after a quiet period.

Verified by executionVariant 1 · 9 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Expiry does not exempt the local client id.

VERIFIED REPAIR

Never expire the entry for self_id.

Unsuccessful approach: Exempting a hard-coded id misses the configured local client id.

Case contract

Presence updates ["update", client, clock, state|None, now] are accepted when clock exceeds the last accepted clock for that client, or when it equals it, the state is None and the client is present. Accepted updates record the clock; a None state removes the client (logging a removal only if it was present); otherwise [state, now] is stored. ["tick", now] removes, in client order, every client other than self_id whose last update is at least timeout old. Return present [client, state] pairs and the removal log.

Why this case matters

Ephemeral presence rides alongside document CRDTs and must neither resurrect departed peers nor expire the local user.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
newer update replaces{'present': [['c1', 'typing']], 'removed': []}{'present': [['c1', 'typing']], 'removed': []}Passed
stale update after timeout is rejected{'present': [], 'removed': ['c1']}{'present': [], 'removed': ['c1']}Passed
offline notice at the same clock removes{'present': [], 'removed': ['c2']}{'present': [], 'removed': ['c2']}Passed
same-clock state change is ignored{'present': [['c2', 'on']], 'removed': []}{'present': [['c2', 'on']], 'removed': []}Passed
timeout boundary{'present': [['c4', 'y']], 'removed': ['c3']}{'present': [['c4', 'y']], 'removed': ['c3']}Passed
own state never expires{'present': [], 'removed': ['me1', 'me']}{'present': [['me1', 'self']], 'removed': ['me']}Failed
activity refreshes the timer{'present': [['c5', 'b']], 'removed': []}{'present': [['c5', 'b']], 'removed': []}Passed
offline notice for an unknown client{'present': [], 'removed': ['c7']}{'present': [], 'removed': ['c7']}Passed
large clocks and short timeout{'present': [], 'removed': ['c8']}{'present': [], 'removed': ['c8']}Passed

SHA-256 / 32d9f51f57549090c99c8c70e57349c089e2770add33ad05c2cfad99d751b715

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != 'me' and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
newer update replaces{'present': [['c1', 'typing']], 'removed': []}{'present': [['c1', 'typing']], 'removed': []}Passed
stale update after timeout is rejected{'present': [], 'removed': ['c1']}{'present': [], 'removed': ['c1']}Passed
offline notice at the same clock removes{'present': [], 'removed': ['c2']}{'present': [], 'removed': ['c2']}Passed
same-clock state change is ignored{'present': [['c2', 'on']], 'removed': []}{'present': [['c2', 'on']], 'removed': []}Passed
timeout boundary{'present': [['c4', 'y']], 'removed': ['c3']}{'present': [['c4', 'y']], 'removed': ['c3']}Passed
own state never expires{'present': [['me', 'other']], 'removed': ['me1']}{'present': [['me1', 'self']], 'removed': ['me']}Failed
activity refreshes the timer{'present': [['c5', 'b']], 'removed': []}{'present': [['c5', 'b']], 'removed': []}Passed
offline notice for an unknown client{'present': [], 'removed': ['c7']}{'present': [], 'removed': ['c7']}Passed
large clocks and short timeout{'present': [], 'removed': ['c8']}{'present': [], 'removed': ['c8']}Passed

SHA-256 / b31471b170e0051b582bbae9c2dc1c603ae51d1135a0bcccd719f24b37596dd3

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, self_id, timeout):
    table = {}
    clocks = {}
    removed = []
    for ev in events:
        if ev[0] == 'update':
            _, c, clk, st, now = ev
            cur = clocks.get(c, -1)
            if clk > cur or (clk == cur and st is None and c in table):
                clocks[c] = clk
                if st is None:
                    if table.pop(c, None) is not None:
                        removed.append(c)
                else:
                    table[c] = [st, now]
        else:
            now = ev[1]
            for c in sorted(table):
                if c != self_id and now - table[c][1] >= timeout:
                    del table[c]
                    removed.append(c)
    return {'present': sorted([c, v[0]] for c, v in table.items()), 'removed': removed}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me1', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me1', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, None, 1]], 'me1', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 1, 'on', 0], ['update', 'c2', 1, 'changed', 1]], 'me1', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me1', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me1', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me1', 30], {'present': [['me1', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me1', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me1', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 101, 's', 3], ['tick', 5], ['tick', 13]], 'me1', 10], {'present': [], 'removed': ['c8']})],
    2: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me2', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me2', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, None, 1]], 'me2', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 2, 'on', 0], ['update', 'c2', 2, 'changed', 1]], 'me2', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me2', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me2', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me2', 30], {'present': [['me2', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me2', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me2', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 102, 's', 3], ['tick', 5], ['tick', 13]], 'me2', 10], {'present': [], 'removed': ['c8']})],
    3: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me3', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me3', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, None, 1]], 'me3', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 3, 'on', 0], ['update', 'c2', 3, 'changed', 1]], 'me3', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me3', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me3', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me3', 30], {'present': [['me3', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me3', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me3', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 103, 's', 3], ['tick', 5], ['tick', 13]], 'me3', 10], {'present': [], 'removed': ['c8']})],
    4: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me4', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me4', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, None, 1]], 'me4', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 4, 'on', 0], ['update', 'c2', 4, 'changed', 1]], 'me4', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me4', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me4', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me4', 30], {'present': [['me4', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me4', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me4', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 104, 's', 3], ['tick', 5], ['tick', 13]], 'me4', 10], {'present': [], 'removed': ['c8']})],
    5: [('newer update replaces', [[['update', 'c1', 1, 'idle', 0], ['update', 'c1', 2, 'typing', 5]], 'me5', 30], {'present': [['c1', 'typing']], 'removed': []}), ('stale update after timeout is rejected', [[['update', 'c1', 3, 'on', 0], ['tick', 30], ['update', 'c1', 3, 'on', 31], ['update', 'c1', 2, 'old', 32]], 'me5', 30], {'present': [], 'removed': ['c1']}), ('offline notice at the same clock removes', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, None, 1]], 'me5', 30], {'present': [], 'removed': ['c2']}), ('same-clock state change is ignored', [[['update', 'c2', 5, 'on', 0], ['update', 'c2', 5, 'changed', 1]], 'me5', 30], {'present': [['c2', 'on']], 'removed': []}), ('timeout boundary', [[['update', 'c3', 1, 'x', 10], ['tick', 39], ['update', 'c4', 1, 'y', 20], ['tick', 40]], 'me5', 30], {'present': [['c4', 'y']], 'removed': ['c3']}), ('own state never expires', [[['update', 'me5', 1, 'self', 0], ['tick', 500], ['update', 'me', 7, 'other', 490], ['tick', 600]], 'me5', 30], {'present': [['me5', 'self']], 'removed': ['me']}), ('activity refreshes the timer', [[['update', 'c5', 1, 'a', 0], ['update', 'c5', 2, 'b', 25], ['tick', 40]], 'me5', 30], {'present': [['c5', 'b']], 'removed': []}), ('offline notice for an unknown client', [[['update', 'c6', 4, None, 0], ['update', 'c6', 3, 'late', 1], ['update', 'c7', 1, 'on', 2], ['update', 'c7', 2, None, 3], ['update', 'c7', 2, None, 4]], 'me5', 30], {'present': [], 'removed': ['c7']}), ('large clocks and short timeout', [[['update', 'c8', 105, 's', 3], ['tick', 5], ['tick', 13]], 'me5', 10], {'present': [], 'removed': ['c8']})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
newer update replaces{'present': [['c1', 'typing']], 'removed': []}{'present': [['c1', 'typing']], 'removed': []}Passed
stale update after timeout is rejected{'present': [], 'removed': ['c1']}{'present': [], 'removed': ['c1']}Passed
offline notice at the same clock removes{'present': [], 'removed': ['c2']}{'present': [], 'removed': ['c2']}Passed
same-clock state change is ignored{'present': [['c2', 'on']], 'removed': []}{'present': [['c2', 'on']], 'removed': []}Passed
timeout boundary{'present': [['c4', 'y']], 'removed': ['c3']}{'present': [['c4', 'y']], 'removed': ['c3']}Passed
own state never expires{'present': [['me1', 'self']], 'removed': ['me']}{'present': [['me1', 'self']], 'removed': ['me']}Passed
activity refreshes the timer{'present': [['c5', 'b']], 'removed': []}{'present': [['c5', 'b']], 'removed': []}Passed
offline notice for an unknown client{'present': [], 'removed': ['c7']}{'present': [], 'removed': ['c7']}Passed
large clocks and short timeout{'present': [], 'removed': ['c8']}{'present': [], 'removed': ['c8']}Passed

SHA-256 / 7a90f56e2d1048b0ab250e1c6cb00437e5785e7438fb263581d1fa05010dcdc5

Verification & scope

A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:05.075155+00:00.

Case digest / 4b311a26b856469f56901b3eb0029fd43d54dde5e176ac65328b30e29c8c4045