Topic: How pending re-queueing in applyremotechange enables multi-hop propagation, and why idempotency via seen is essential to prevent infinite loops

Date: 2026-05-29

Time: 09:05

Multi-Hop Propagation via pending and Idempotency via seen

The Core Mechanism

In a multi-leader replication cluster, a write originating at node A must eventually reach *every* node — not just A's direct neighbors. In a ring topology, node A only talks to node B, which talks to node C, and so on. The write has to "hop" through intermediaries. The pending queue and seen set work together to make this happen safely.

How _pending re-queueing enables forwarding

When a node receives a remote change via applyremotechange (multi-leader-replication/multileader.py:94), it doesn't just apply the change locally — it re-enqueues the change into its own pending list so it will be forwarded to the next node during the next replication cycle.

This happens in three places within applyremotechange:

1. No local value exists (line 118): The node accepts the change and immediately appends it to _pending:

`python

self._pending.append(change)

`

2. Same-origin update, no conflict (line 136): The newer version wins, and the change is re-queued:

`python

self._pending.append(change)

`

3. Conflict with custom merge (line 170): After merging, a *new* change (with the merged value, a fresh timestamp, and a canonical origin) is appended to _pending.

4. Conflict with LWW (line 192, the final self._pending.append(change) after the conflict block): The original change is forwarded as-is.

The getpendingchanges method (line 88) atomically drains this queue — returning all accumulated changes and resetting _pending to empty. The MultiLeaderCluster orchestrator then delivers these drained changes to the next node(s) in the topology.

This is the multi-hop engine: Node A writes → change lands in A's pending → cluster delivers to B → B's applyremotechange applies it *and* re-enqueues to B's pending → cluster delivers to C → and so on until every node has the change.

Why _seen is essential

Without idempotency, this re-queueing creates infinite loops. Consider a three-node ring A → B → C → A:

1. A writes key "x" at timestamp 1

2. A's change propagates to B, B re-queues it

3. B's change propagates to C, C re-queues it

4. C's change propagates back to A — and without _seen, A would re-queue it again

5. A propagates to B again, B re-queues... infinite loop

The seen dictionary (multileader.py:42) prevents this:


self._seen: dict[str, set[tuple[int, str]]] = {}

It maps each key to a set of (timestamp, originnodeid) pairs that this node has already processed. The idempotency check at line 104 is the first thing applyremotechange does after extracting the change fields:


if key in self._seen and (remote_ts, remote_node) in self._seen[key]:
    return None

When node A originally wrote key "x", it called recordseen(key, ts, self.nodeid) at line 57. So when C's forwarded copy of that same change arrives back at A, the (timestamp=1, origin="A") pair is already in A's seen["x"] set. The change is silently dropped — no re-queueing, no conflict resolution, no further propagation. The loop dies.

The recordseen helper

Every path that accepts a change calls recordseen (line 48–51):


def _record_seen(self, key: str, ts: int, origin: str):
    if key not in self._seen:
        self._seen[key] = set()
    self._seen[key].add((ts, origin))

This is called:

The custom-merge complication

When a conflict is resolved via CUSTOM_MERGE (lines 160–177), the merged result gets a new timestamp and canonical origin. This means the merged change is a genuinely new (ts, origin) pair that no node has seen before, so it will propagate through the full ring without being dropped. This is correct — every node needs the merged result, not the original conflicting values.

Topics to Explore

Beliefs