Partition-Tolerant Share Routing in Python

When a network partition splits your MPC custodians mid-round, the dangerous outcome is not a stalled computation — it is a round that quietly completes from a partial or duplicated set of shares and hands a wrong coordinate to the analytics layer. This page builds a small asyncio share-router that distributes secret-share envelopes across compute nodes and stays provably correct under partitions by obeying one rule: prefer to stall a round (fail-closed) over reconstructing below quorum. It is the correctness-focused companion to the broader async routing for MPC guide inside the Secure Multi-Party Computation in Spatial Analytics architecture, and it assumes each envelope already wraps a masked additive or Shamir fragment produced by the secret sharing for coordinates layer. Where the parent guide covers the broker topology, wire framing, and HMAC integrity, this page is narrower: the in-process control loop that decides when a round is allowed to complete.

Parameter Configuration and Calibration

A partition-tolerant router is defined almost entirely by six knobs. Each one trades availability against the fail-closed guarantee, and none is a pure performance dial — a mis-set retry budget or a missing round nonce is a correctness bug that reconstructs a plausible-but-wrong point. Because a tt-of-nn scheme completes from any quorum of tt acks, the router never needs every node; it needs exactly enough, and it must refuse to proceed on anything less.

Knob Typical value Rationale — the correctness/availability trade-off
quorum (tt) 2 of 3, 3 of 5 The hard floor. collect returns only once ∣acks∣≥t\lvert\text{acks}\rvert \ge t; below it the round must raise, never return a partial set.
per_share_timeout 1–3 s Ceiling on a single asyncio.wait_for send attempt. Too high wedges the event loop behind a dark node; too low burns the retry budget on healthy-but-slow links.
retry_budget 3–5 attempts Max attempts per envelope. When exhausted the node is simply absent from the ack set — quorum, not this node, decides the round.
base_backoff / max_backoff 50 ms → 1.5 s Exponential backoff bounds. Doubling per attempt, capped, so a flapping node cannot be hammered into a synchronised retry storm.
jitter full jitter Retry delay sampled uniformly from [0,backoff][0, \text{backoff}] to decorrelate concurrent retries across nodes (the AWS “full jitter” rule).
round_deadline 5–10 s Hard wall on collect. At the deadline with fewer than tt acks the router fails closed with RoundStalled; half-way through it escalates to a backup quorum.

Two invariants tie the knobs together. First, the round nonce: every envelope carries the nonce of the round it belongs to, and a share whose nonce does not match the router’s current nonce for that round is rejected without an ack. This is what makes a captured share from an earlier round — or a naive replay — inert rather than corrupting. Second, idempotent delivery: at-least-once transport means a backup node and a recovering primary can both ack the same logical custodian, so the router dedups by (round_id, node_id) and counts each custodian once. Size retry_budget × max_backoff to stay comfortably under round_deadline, or a node will still be retrying when the deadline fires and the escalation window will never open.

Partition-tolerant routing state machine — dispatch, await acks with backoff, quorum decides complete vs. backup vs. fail-closed, with a stale-nonce reject path A state-machine diagram. From a small "Round open" start state an arrow reaches "Dispatch envelopes" (one send per node). An arrow leads right to "Await acks", which carries a self-loop labelled timeout to backoff plus jitter, retry at most the budget. From Await acks an arrow reaches a "Quorum >= t ?" decision. On the "at least t" branch a rightward arrow reaches "Round complete", which hands off reconstruction. On the "fewer than t at the halfway mark" branch a downward arrow reaches "Escalate: backup quorum", from which a re-dispatch arrow loops back up into Await acks. From Escalate, if the deadline passes still short of t, an arrow reaches "Fail-closed: RoundStalled". Separately, a downward arrow from Dispatch envelopes reaches "Reject envelope: stale or replayed nonce, no ack", a terminal guard that keeps stale shares out of the ack set. Partition-tolerant share routing — quorum decides complete vs. backup vs. fail-closed timeout → backoff + jitter (retry ≤ budget) ≥ t < t at t/2 escalate re-dispatch to backups deadline still < t nonce ≠ round nonce Round open Dispatch envelopes one send per node wait_for timeout Await acks dedup (round, node) idempotent delivery Quorum ≥ t ? count distinct acks t-of-n, not all-of-n Round complete hand off reconstruction to the MPC kernel Escalate: backup quorum re-send to dark nodes' backup transports Fail-closed raise RoundStalled no partial reconstruct Reject envelope stale / replayed nonce no ack · never counts

Reference Implementation

The ShareRouter below is the whole control loop: distribute(envelopes) fans envelopes out to their nodes with a per-share asyncio.wait_for timeout and jittered exponential backoff, and collect(round_id, quorum) returns the acked node set once quorum is reached or raises RoundStalled at the deadline. Delivery is idempotent — dedup is keyed on (round_id, node_id) — and every envelope is checked against the round nonce before it can ack. Nothing here touches plaintext geometry; the router moves opaque masked shares and reasons only about how many distinct custodians have acknowledged.

python
from __future__ import annotations

import asyncio
import random
from dataclasses import dataclass
from typing import Awaitable, Callable, Dict, List, Optional, Sequence, Set, Tuple


class RoundStalled(Exception):
    """Fail-closed signal: a round could not reach quorum and must NOT reconstruct."""


class StaleShareRejected(Exception):
    """An envelope carried a nonce from an old or replayed round — reject, do not ack."""


@dataclass(frozen=True)
class ShareEnvelope:
    """One masked secret-share bound to a round. `payload` is opaque — never plaintext."""
    round_id: str
    node_id: int
    nonce: int          # per-round nonce; a mismatch means stale/replayed → rejected
    payload: bytes


# A transport delivers one envelope to a node and returns the serviced node_id,
# or raises (ConnectionError/TimeoutError) when the node is unreachable.
NodeTransport = Callable[[ShareEnvelope], Awaitable[int]]


@dataclass
class RouterConfig:
    quorum: int                       # t — distinct acks required to complete
    total_nodes: int                  # n — primary custodians
    per_share_timeout: float = 2.0    # ceiling on one wait_for send attempt (s)
    retry_budget: int = 4             # max attempts per envelope before giving up
    base_backoff: float = 0.05        # first retry delay (s)
    max_backoff: float = 1.5          # backoff ceiling (s)
    round_deadline: float = 8.0       # hard wall for collect() (s)

    def __post_init__(self) -> None:
        if not (1 <= self.quorum <= self.total_nodes):
            raise ValueError("require 1 <= quorum <= total_nodes")


class ShareRouter:
    """Distributes share envelopes across MPC nodes and completes a round only
    once a t-of-n quorum acks. On partition it fails closed rather than
    reconstructing from a partial or duplicated set of shares."""

    def __init__(self, primary: Dict[int, NodeTransport],
                 backup: Optional[Dict[int, NodeTransport]],
                 config: RouterConfig) -> None:
        self.primary: Dict[int, NodeTransport] = dict(primary)
        self.backup: Dict[int, NodeTransport] = dict(backup or {})
        self.cfg: RouterConfig = config
        self._nonce: Dict[str, int] = {}                 # round_id -> current nonce
        self._acked: Dict[str, Set[int]] = {}            # round_id -> node_ids acked
        self._pending: Dict[str, List[ShareEnvelope]] = {}  # for backup escalation
        self._delivered: Set[Tuple[str, int]] = set()    # (round, node) idempotency key
        self._lock: asyncio.Lock = asyncio.Lock()

    def open_round(self, round_id: str, nonce: int) -> None:
        """Register the authoritative nonce for a round before any dispatch."""
        self._nonce[round_id] = nonce
        self._acked.setdefault(round_id, set())

    def _jittered(self, backoff: float) -> float:
        # Full jitter: sample in [0, backoff] so concurrent retries decorrelate
        # instead of stampeding a recovering node in lockstep.
        return random.uniform(0.0, backoff)

    async def _deliver_one(self, transports: Dict[int, NodeTransport],
                           env: ShareEnvelope) -> None:
        """Deliver a single envelope with timeout + backoff. Records an ack on
        success; silently gives up (leaving the node absent) on exhaustion."""
        # Round-nonce guard: a stale/replayed share must never count toward quorum.
        if env.nonce != self._nonce.get(env.round_id):
            raise StaleShareRejected(f"stale nonce for round {env.round_id}")
        transport = transports.get(env.node_id)
        if transport is None:
            return
        backoff = self.cfg.base_backoff
        for attempt in range(1, self.cfg.retry_budget + 1):
            try:
                serviced = await asyncio.wait_for(transport(env), self.cfg.per_share_timeout)
            except (asyncio.TimeoutError, ConnectionError, OSError):
                if attempt >= self.cfg.retry_budget:
                    return  # node stays dark; the QUORUM, not this node, decides
                await asyncio.sleep(self._jittered(backoff))
                backoff = min(self.cfg.max_backoff, backoff * 2)  # exponential
                continue
            async with self._lock:
                key = (env.round_id, serviced)
                if key in self._delivered:
                    return  # idempotent: a duplicate or backup ack counts ONCE
                self._delivered.add(key)
                self._acked.setdefault(env.round_id, set()).add(serviced)
            return

    async def distribute(self, envelopes: Sequence[ShareEnvelope]) -> None:
        """Fan out envelopes to primary nodes; never block the round on one node."""
        if envelopes:
            self._pending.setdefault(envelopes[0].round_id, []).extend(envelopes)
        await asyncio.gather(
            *(self._deliver_one(self.primary, e) for e in envelopes),
            return_exceptions=True,  # a StaleShareRejected here is swallowed by design
        )

    async def _escalate(self, round_id: str, acked: Set[int]) -> None:
        """Re-dispatch outstanding envelopes to backup transports for dark nodes."""
        outstanding = [e for e in self._pending.get(round_id, [])
                       if e.node_id not in acked and e.node_id in self.backup]
        await asyncio.gather(
            *(self._deliver_one(self.backup, e) for e in outstanding),
            return_exceptions=True,
        )

    async def collect(self, round_id: str, quorum: int) -> Set[int]:
        """Return the acked node set once >= quorum acks land, else raise RoundStalled.

        FAIL-CLOSED CONTRACT: this method returns ONLY a genuine t-of-n quorum.
        Under a partition it raises rather than returning a partial set, so a
        caller can never reconstruct a coordinate from too few (or duplicated) shares.
        """
        loop = asyncio.get_event_loop()
        deadline = loop.time() + self.cfg.round_deadline
        escalate_at = loop.time() + self.cfg.round_deadline / 2
        escalated = False
        while True:
            acked = self._acked.get(round_id, set())
            if len(acked) >= quorum:
                return set(acked)  # quorum reached — safe to reconstruct
            now = loop.time()
            if not escalated and now >= escalate_at and self.backup:
                escalated = True
                await self._escalate(round_id, acked)  # try the backup quorum
            if now >= deadline:
                raise RoundStalled(
                    f"round {round_id}: {len(acked)}/{quorum} acks at deadline")
            await asyncio.sleep(0.02)  # yield; let in-flight deliveries land

The load-bearing detail is that a node exhausting its retry budget returns from _deliver_one without an ack — it is simply missing from _acked, and collect treats a missing node exactly like a slow one: it never lowers quorum to accommodate it. That is what turns “one custodian is unreachable” into a completed round and “too many custodians are unreachable” into a clean RoundStalled rather than a silent partial reconstruction.

Validation Checkpoint

The harness runs three partition scenarios under asyncio.run and asserts the fail-closed contract holds in each. It uses in-process fake transports — a healthy node acks immediately, a dark node always raises ConnectionError — so it is safe in CI with no broker.

python
def _make_transport(node_id: int, *, dark: bool = False,
                    delay: float = 0.0) -> NodeTransport:
    async def _t(env: ShareEnvelope) -> int:
        await asyncio.sleep(delay)
        if dark:
            raise ConnectionError(f"node {node_id} unreachable")
        return env.node_id
    return _t


async def _run() -> None:
    cfg = RouterConfig(quorum=2, total_nodes=3, per_share_timeout=0.2,
                       retry_budget=2, base_backoff=0.01, max_backoff=0.05,
                       round_deadline=0.8)

    # 1. One node goes dark — the round STILL completes on a 2-of-3 quorum.
    primary = {1: _make_transport(1), 2: _make_transport(2),
               3: _make_transport(3, dark=True)}
    r1 = ShareRouter(primary, backup=None, config=cfg)
    r1.open_round("rnd-1", nonce=1001)
    await r1.distribute([ShareEnvelope("rnd-1", n, 1001, b"\x00") for n in (1, 2, 3)])
    acked = await r1.collect("rnd-1", quorum=2)
    assert len(acked) >= 2 and 3 not in acked   # dropped node absent, round OK

    # 2. Full partition — collect FAILS CLOSED instead of returning a partial set.
    dead = {n: _make_transport(n, dark=True) for n in (1, 2, 3)}
    r2 = ShareRouter(dead, backup=None, config=cfg)
    r2.open_round("rnd-2", nonce=2002)
    await r2.distribute([ShareEnvelope("rnd-2", n, 2002, b"\x00") for n in (1, 2, 3)])
    try:
        await r2.collect("rnd-2", quorum=2)
    except RoundStalled:
        pass
    else:
        raise AssertionError("full partition must raise, never return a partial quorum")

    # 3. Replayed / stale envelopes are ignored — quorum count is unaffected.
    r3 = ShareRouter({1: _make_transport(1)}, backup=None, config=cfg)
    r3.open_round("rnd-3", nonce=3003)
    good = ShareEnvelope("rnd-3", 1, 3003, b"\x00")
    await r3.distribute([good])
    before = len(r3._acked["rnd-3"])
    await r3.distribute([ShareEnvelope("rnd-3", 1, 9999, b"\x00")])  # stale nonce
    await r3.distribute([good])                                      # exact replay
    after = len(r3._acked["rnd-3"])
    assert before == after == 1   # stale rejected; duplicate deduped — counted once

    print("all partition-tolerant routing invariants hold")


def _validate() -> None:
    asyncio.run(_run())


if __name__ == "__main__":
    _validate()

Each assertion maps to a production guarantee: scenario 1 proves availability under single-node loss, scenario 2 proves the fail-closed floor under a total partition, and scenario 3 proves that the round nonce plus (round_id, node_id) dedup make replays and duplicate deliveries inert. Wire all three into CI — the failures they catch are silent in production, exactly the class of bug the secret sharing for coordinates guide flags where a wrong-but-plausible coordinate is worse than an error.

Incident Response and Edge Cases

  • Asymmetric partition — one side sees acks, the other times out. A node receives an envelope and processes it, but its ack is lost on the return path. The router’s retry re-sends and the node re-processes; without idempotency this double-counts or corrupts state. Remediation: the (round_id, node_id) dedup already collapses the duplicate ack, but the node must also treat a redelivered envelope as idempotent (upsert its share by index, never append), so a lost-ack retry cannot inflate a reconstruction set.
  • Escalation storm on a flapping backup. A primary and its backup both flap, so collect escalates, the backup half-acks, and retries stampede. Remediation: the full-jitter backoff already decorrelates retries; additionally cap retry_budget so total attempts across primary + backup stay within round_deadline, and alert when the escalation path fires more than once per round — that is a topology problem, not a transient.
  • Nonce reuse across rounds. Re-opening a round with a previously used nonce lets a captured envelope from the old round pass the guard and ack. Remediation: draw nonces from a strictly monotonic or CSPRNG source per round and never reissue; treat open_round with a seen nonce as a provisioning error. The same round-nonce discipline governs re-distribution in the parent async routing for MPC guide.
  • Quorum met but round semantically stale. Enough nodes ack, but round_deadline was set longer than the downstream compute’s freshness window, so the reconstructed coordinate is already outdated when handed off. Remediation: set round_deadline to the minimum of the availability tolerance and the data-freshness/retention window, so a late-but-valid quorum is dead-lettered rather than reconstructed after its useful life.

Frequently Asked Questions

Why fail closed instead of reconstructing from whatever shares arrived?

Because a $t$-of-$n$ scheme is only secure and correct at the threshold: fewer than $t$ genuine shares cannot reconstruct the true value, and mixing in a duplicated or stale share yields a wrong-but-plausible coordinate with no error raised. Stalling the round surfaces the partition as a `RoundStalled` exception the operator can act on; a partial reconstruction silently poisons the analytics output. Fail-closed is the only default that preserves the guarantee the secret-sharing layer was chosen to provide.

How does a t-of-n quorum let a round complete without every node?

The router counts distinct acks and returns as soon as $t$ of them land, so up to $n-t$ nodes can be dark and the round still completes — a $(2,3)$ scheme tolerates one loss, a $(3,5)$ scheme two. A node that exhausts its retry budget is simply absent from the ack set; `collect` never lowers the quorum to include it. This is what makes the router partition-tolerant on the availability side while still fail-closed below the threshold.

When does the backup quorum get used instead of the primary?

`collect` escalates once, at the halfway point of `round_deadline`, and only if fewer than $t$ acks have landed and backup transports are configured. It re-dispatches the outstanding envelopes for dark nodes to their backup transports; those acks flow into the same dedup-guarded set, so a primary that recovers and its backup cannot both be counted. If escalation still does not reach quorum by the deadline, the round fails closed.

Do the round nonce and idempotency key replace HMAC integrity?

No — they are orthogonal. The round nonce rejects stale and replayed envelopes and the `(round_id, node_id)` key deduplicates at-least-once delivery, but neither authenticates the payload. Envelope integrity still comes from the HMAC framing in the parent async-routing guide; this router assumes shares are already authenticated and concerns itself only with when a round is allowed to complete.

Up: Async Routing for MPC · Secure Multi-Party Computation in Spatial Analytics