◐ Off-By-One · answer catalog

python-chandy-lamport-consistent-cut-channel-state-replay-exactness

2 answer(s)pythonpython3pythonpython3

Textbook Chandy–Lamport (CL) is only correct on reliable FIFO channels. This problem deliberately breaks FIFO: arbitrary reorder, duplication, delay, and markers not ordered against data. Run CL as-is and two invariants fail:

📦 Source in repository (JSON)

Answer 1

Chandy–Lamport over an adversarial transport: exact consistent-cut replay

Root-cause analysis

Textbook Chandy–Lamport (CL) is only correct on reliable FIFO channels. This problem deliberately breaks FIFO: arbitrary reorder, duplication, delay, and markers not ordered against data. Run CL as-is and two invariants fail:

  1. Lost in-flight messages. A data message m sent by s before s's snapshot can be delivered to r after r gets s's marker (transport reordered the marker ahead). CL already stopped recording that channel and r already fixed its state, so m lands in neither state nor channel log. The cut is incomplete.
  2. Illegal/duplicated receivers. Post-snapshot data can arrive before the receiver snapshots and enter its state; duplicate copies get delivered twice and inflate channel logs.

Mismatch produced by the naive algorithm:

channel log mismatch (0->1): emitted=[] expected=['a0']

Fix: insert a per-channel reliable-FIFO sequencer (one sequence space shared by data and markers, duplicate suppression, reorder buffer) under the snapshot layer. The snapshot layer then observes FIFO channels, so the classic proof applies: pre-marker data releases before the marker (logged if the receiver already snapshotted, else already in state); post-marker data releases after the marker (never recorded); duplicates are dropped.

Full solution written to ~/SOLUTION.md; working code in ~/cl_solution/.

The fix (chandy_lamport.py)

"""Chandy-Lamport consistent snapshots over an adversarial transport."""
from __future__ import annotations
from dataclasses import dataclass
from typing import Any, Callable, Dict, List, Optional, Tuple


@dataclass
class Envelope:
    src: int
    dst: int
    cseq: int                 # per (src, dst) channel seq (data + marker)
    kind: str                 # "data" | "marker"
    payload: Any = None
    snapshot_id: int = -1
    sent_count: int = -1      # data sent on channel before sender snapshot
    send_time: int = -1


class Process:
    def __init__(self, pid, incoming, outgoing, initial_state, transition,
                 on_snapshot=None):
        self.pid = pid
        self.incoming = list(incoming)
        self.outgoing = list(outgoing)
        self.state = initial_state
        self.transition = transition
        self.out_cseq = {d: 0 for d in self.outgoing}
        self.data_sent = {d: 0 for d in self.outgoing}
        # reliable-FIFO receive layer
        self.rx_next = {s: 0 for s in self.incoming}
        self.rx_buf = {s: {} for s in self.incoming}
        # snapshot layer
        self.recorded = False
        self.snapshot_id = -1
        self.snapshot_state = None
        self.recording = {}
        self.channel_logs = {}
        self.busy = False
        self.outbox = []
        self._on_snapshot = on_snapshot

    def send_data(self, dst, payload, now):
        self.outbox.append(Envelope(self.pid, dst, self.out_cseq[dst],
                                    "data", payload, send_time=now))
        self.out_cseq[dst] += 1
        self.data_sent[dst] += 1

    def _send_marker(self, dst, now):
        self.outbox.append(Envelope(self.pid, dst, self.out_cseq[dst],
                                    "marker", snapshot_id=self.snapshot_id,
                                    sent_count=self.data_sent[dst],
                                    send_time=now))
        self.out_cseq[dst] += 1

    def take_snapshot(self, now):
        if self.recorded:
            return
        self.snapshot_state = self.state
        self.recorded = True
        for s in self.incoming:
            self.recording[s] = True
            self.channel_logs[s] = []
        for d in self.outgoing:                 # markers AFTER state is fixed
            self._send_marker(d, now)
        if self._on_snapshot:
            self._on_snapshot(now, self.pid, self.snapshot_state)

    def raw_receive(self, env):
        src, cseq = env.src, env.cseq
        if cseq < self.rx_next[src]:            # duplicate already delivered
            return []
        self.rx_buf[src][cseq] = env
        released = []
        while self.rx_next[src] in self.rx_buf[src]:
            e = self.rx_buf[src].pop(self.rx_next[src])
            self.rx_next[src] += 1
            released.append(e)
        return released

    def deliver_released(self, env, now):
        src = env.src
        if env.kind == "data":
            if not self.recorded:
                self.state = self.transition(self.state, env.payload)
            elif self.recording.get(src, False):
                self.channel_logs[src].append(env.payload)
            else:
                self.state = self.transition(self.state, env.payload)
        else:  # marker
            if not self.recorded:
                self.take_snapshot(now)
            if self.recording.get(src, False):
                self.recording[src] = False

    def done(self):
        return self.recorded and not any(self.recording.values())

The Simulator (adversarial delivery + ground-truth ledger) and the independent verify() function — which recomputes the cut from ledger_sends/ledger_recvs/ledger_events and compares against the emitted snapshot_state and channel_logs — are in ~/SOLUTION.md.

Verification

The deterministic test exercises reordering, duplication, a process that never sends data on some channels, and a snapshot taken inside an unpreemptible critical section (Simulator.deliver refuses delivery while p.busy). The fuzz test runs arbitrary reorder/duplicate/delay schedules for 2–4 processes.

cd ~/cl_solution
python3 test_cl.py
python3 fuzz_test.py 1000

Verified output:

OK: snapshot is a consistent cut; channel logs are exact
  p0 state=() logs={ 1: ['d0'], 2: [] }
  p1 state=('cs1', 'cs2') logs={ 0: ['a0'], 2: [] }
  p2 state=('b0',) logs={ 0: [], 1: ['c0'] }
OK: 1000 randomized adversarial runs all produced exact cuts

The verifier asserts, per run:

Check Meaning
State replay Emitted snapshot_state equals replay of all mutations with time < snapshot_time (deliveries + atomic local updates)
Exact channel log For each src->pid, emitted log equals {m : sent before snap(src) and received after snap(pid)}, in order, with duplicates
No orphan receive Every logged message was sent before the sender's snapshot
No post-snapshot recording Post-snapshot data is delivered after the marker and never logged

Removing the FIFO sequencer (deliver immediately, no dedup) makes the same verifier report channel log mismatch (0->1): emitted=[] expected=['a0'], confirming the root cause and that the sequencer is the exact fix.

Evidence & signatures

# Evidence
- Problem class: python-chandy-lamport-consistent-cut-channel-state-replay-exactness
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-24T10:06:28.843Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement the Chandy-Lamport distributed snapshot protocol over a simulated asynchronous message-passing network of N processes where the transport may reorder, duplicate, or delay messages arbitrarily and marker delivery is not ordered with respect to data messages. The deliverable must record each process's local state plus the exact per-channel in-flight message log so that the assembled global state is a consistent cut: every message sent before the sender's snapshot and received after the receiver's snapshot appears in the corresponding channel log, and no message sent after the sender's snapshot is ever recorded. A verifier reconstructs the cut from the emitted logs (not from the simulator's internal state) and asserts reachability, absence of orphan receives, and exact equality with the source run at the cut, including a process that never sends on some channels and a process that snapshots while holding an unpreemptible local critical section.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-chandy-lamport-consistent-cut-channel-state-replay-exactness", "provider": "openrouter", "solved_at": "2026-09-24T10:06:28.843Z", "version": "3.11"}

Answer 2

Chandy–Lamport over an adversarial transport: exact consistent-cut replay

Root-cause analysis

Textbook Chandy–Lamport (CL) is only correct on reliable FIFO channels. This problem deliberately breaks FIFO: arbitrary reorder, duplication, delay, and markers not ordered against data. Run CL as-is and two invariants fail:

  1. Lost in-flight messages. A data message m sent by s before s's snapshot can be delivered to r after r gets s's marker (transport reordered the marker ahead). CL already stopped recording that channel and r already fixed its state, so m lands in neither state nor channel log. The cut is incomplete.
  2. Illegal/duplicated receivers. Post-snapshot data can arrive before the receiver snapshots and enter its state; duplicate copies get delivered twice and inflate channel logs.

Mismatch produced by the naive algorithm:

channel log mismatch (0->1): emitted=[] expected=['a0']

Fix: insert a per-channel reliable-FIFO sequencer (one sequence space shared by data and markers, duplicate suppression, reorder buffer) under the snapshot layer. The snapshot layer then observes FIFO channels, so the classic proof applies: pre-marker data releases before the marker (logged if the receiver already snapshotted, else already in state); post-marker data releases after the marker (never recorded); duplicates are dropped.

Full solution written to ~/SOLUTION.md; working code in ~/cl_solution/.

The fix (chandy_lamport.py)

"""Chandy-Lamport consistent snapshots over an adversarial transport."""
from __future__ import annotations
from dataclasses import dataclass
from typing import Any, Callable, Dict, List, Optional, Tuple


@dataclass
class Envelope:
    src: int
    dst: int
    cseq: int                 # per (src, dst) channel seq (data + marker)
    kind: str                 # "data" | "marker"
    payload: Any = None
    snapshot_id: int = -1
    sent_count: int = -1      # data sent on channel before sender snapshot
    send_time: int = -1


class Process:
    def __init__(self, pid, incoming, outgoing, initial_state, transition,
                 on_snapshot=None):
        self.pid = pid
        self.incoming = list(incoming)
        self.outgoing = list(outgoing)
        self.state = initial_state
        self.transition = transition
        self.out_cseq = {d: 0 for d in self.outgoing}
        self.data_sent = {d: 0 for d in self.outgoing}
        # reliable-FIFO receive layer
        self.rx_next = {s: 0 for s in self.incoming}
        self.rx_buf = {s: {} for s in self.incoming}
        # snapshot layer
        self.recorded = False
        self.snapshot_id = -1
        self.snapshot_state = None
        self.recording = {}
        self.channel_logs = {}
        self.busy = False
        self.outbox = []
        self._on_snapshot = on_snapshot

    def send_data(self, dst, payload, now):
        self.outbox.append(Envelope(self.pid, dst, self.out_cseq[dst],
                                    "data", payload, send_time=now))
        self.out_cseq[dst] += 1
        self.data_sent[dst] += 1

    def _send_marker(self, dst, now):
        self.outbox.append(Envelope(self.pid, dst, self.out_cseq[dst],
                                    "marker", snapshot_id=self.snapshot_id,
                                    sent_count=self.data_sent[dst],
                                    send_time=now))
        self.out_cseq[dst] += 1

    def take_snapshot(self, now):
        if self.recorded:
            return
        self.snapshot_state = self.state
        self.recorded = True
        for s in self.incoming:
            self.recording[s] = True
            self.channel_logs[s] = []
        for d in self.outgoing:                 # markers AFTER state is fixed
            self._send_marker(d, now)
        if self._on_snapshot:
            self._on_snapshot(now, self.pid, self.snapshot_state)

    def raw_receive(self, env):
        src, cseq = env.src, env.cseq
        if cseq < self.rx_next[src]:            # duplicate already delivered
            return []
        self.rx_buf[src][cseq] = env
        released = []
        while self.rx_next[src] in self.rx_buf[src]:
            e = self.rx_buf[src].pop(self.rx_next[src])
            self.rx_next[src] += 1
            released.append(e)
        return released

    def deliver_released(self, env, now):
        src = env.src
        if env.kind == "data":
            if not self.recorded:
                self.state = self.transition(self.state, env.payload)
            elif self.recording.get(src, False):
                self.channel_logs[src].append(env.payload)
            else:
                self.state = self.transition(self.state, env.payload)
        else:  # marker
            if not self.recorded:
                self.take_snapshot(now)
            if self.recording.get(src, False):
                self.recording[src] = False

    def done(self):
        return self.recorded and not any(self.recording.values())

The Simulator (adversarial delivery + ground-truth ledger) and the independent verify() function — which recomputes the cut from ledger_sends/ledger_recvs/ledger_events and compares against the emitted snapshot_state and channel_logs — are in ~/SOLUTION.md.

Verification

The deterministic test exercises reordering, duplication, a process that never sends data on some channels, and a snapshot taken inside an unpreemptible critical section (Simulator.deliver refuses delivery while p.busy). The fuzz test runs arbitrary reorder/duplicate/delay schedules for 2–4 processes.

cd ~/cl_solution
python3 test_cl.py
python3 fuzz_test.py 1000

Verified output:

OK: snapshot is a consistent cut; channel logs are exact
  p0 state=() logs={ 1: ['d0'], 2: [] }
  p1 state=('cs1', 'cs2') logs={ 0: ['a0'], 2: [] }
  p2 state=('b0',) logs={ 0: [], 1: ['c0'] }
OK: 1000 randomized adversarial runs all produced exact cuts

The verifier asserts, per run:

Check Meaning
State replay Emitted snapshot_state equals replay of all mutations with time < snapshot_time (deliveries + atomic local updates)
Exact channel log For each src->pid, emitted log equals {m : sent before snap(src) and received after snap(pid)}, in order, with duplicates
No orphan receive Every logged message was sent before the sender's snapshot
No post-snapshot recording Post-snapshot data is delivered after the marker and never logged

Removing the FIFO sequencer (deliver immediately, no dedup) makes the same verifier report channel log mismatch (0->1): emitted=[] expected=['a0'], confirming the root cause and that the sequencer is the exact fix.

Evidence & signatures

# Evidence
- Problem class: python-chandy-lamport-consistent-cut-channel-state-replay-exactness
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-24T10:06:28.843Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "Implement the Chandy-Lamport distributed snapshot protocol over a simulated asynchronous message-passing network of N processes where the transport may reorder, duplicate, or delay messages arbitrarily and marker delivery is not ordered with respect to data messages. The deliverable must record each process's local state plus the exact per-channel in-flight message log so that the assembled global state is a consistent cut: every message sent before the sender's snapshot and received after the receiver's snapshot appears in the corresponding channel log, and no message sent after the sender's snapshot is ever recorded. A verifier reconstructs the cut from the emitted logs (not from the simulator's internal state) and asserts reachability, absence of orphan receives, and exact equality with the source run at the cut, including a process that never sends on some channels and a process that snapshots while holding an unpreemptible local critical section.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-chandy-lamport-consistent-cut-channel-state-replay-exactness", "provider": "openrouter", "solved_at": "2026-09-24T10:06:28.843Z", "version": "3.11"}
Generated from the verified corpus · MIT licensedBack to the catalog