C13: Partial failures, retries, and distributed consistency

A. Prerequisites and observable goals#

Level: Degree core introduction; no distributed consensus implementation or deployment claim.

B. The central question: what do you know after silence?#

A local call is analyzed within one process and may return, raise, or fail to terminate. A remote call introduces another process, a network, persistent state, and uncertainty about their relative progress. A timeout says a deadline passed without the expected response. It does not distinguish a request that never arrived from a request that committed but whose reply was lost.

The dashed arrow represents a simulated missing reply, not evidence that the service rolled back. The retry must preserve the operation’s identity. Generating a new key for every transmission defeats deduplication because the service sees different logical operations.

An idempotent operation has the same relevant effect when repeated as when performed once. Assigning a resource’s desired state can be idempotent under appropriate semantics; incrementing a balance generally is not. HTTP’s method-level idempotence is a semantic contract, not a guarantee that arbitrary application code behaves correctly. Even an idempotent effect may produce different responses over time; define what your API promises. [HTTP]

C. Build a deduplication invariant, not a slogan#

For each logical request key, store a fingerprint of the normalized payload and the result. If the key already exists with the same fingerprint, return the stored result without reapplying the change. If it exists with a different fingerprint, reject the conflict. If it is new, apply the effect and record the key/result in the same durable transaction.

Why the same transaction? Recording the key first can lose the effect after a crash: a retry finds a completed-looking record and skips work never performed. Applying the effect first can duplicate it after a crash: a retry finds no record and applies it again. Atomic commit removes this gap within the database’s durability and isolation guarantees. External side effects, such as sending an email through another service, do not automatically become part of that transaction. An outbox pattern records a pending message in the transaction; its delivery still requires a receiver-side deduplication or other explicit semantic policy.

The desired invariant is: a committed request record corresponds to exactly one committed application of that logical operation, and subsequent matching retries reuse its result. This is a statement about the defined operation and retention period, not a magical guarantee of exactly-once delivery over an unreliable network. Expiring request records changes the guarantee: a very late retry may become indistinguishable from a new request.

D. Retries can amplify an outage#

A bounded retry policy considers an overall deadline, maximum attempts, exponential delay, randomized jitter, and which errors are retryable. Retrying a malformed request is unlikely to help. Retrying every request immediately after a server slowdown increases load precisely when capacity is constrained. Queue bounds and admission control turn overload into explicit rejection or deferred work instead of unbounded memory growth.

Suppose an operation receives at most three attempts. Even if each attempt independently succeeds with probability $p$, the chance of at least one success would be $1-(1-p)^3$. Real outage failures are often correlated, so this simple model should not justify aggressive retries. Observe attempt counts and total logical operations separately: a surge in request rate may be retry amplification rather than new demand.

Caching and replication also require semantics. A cache can serve stale data; its time-to-live is not a proof that a value is current. A replicated log can improve fault tolerance, but replicas may lag. Read-your-writes, causal consistency, sequential consistency, and linearizability are different contracts. Linearizability asks whether each operation can be placed at one instant between invocation and response in an order respecting real-time precedence. It is stronger than merely returning some value that was once stored.

E. Clocks and agreement#

Wall clocks can disagree or move because of adjustments. A timestamp alone does not prove that one event caused another. A happens-before relation orders events within a process and from message send to corresponding receive, then closes transitively. Lamport-style logical clocks can preserve this order: if $a$ happens before $b$, then $L(a)<L(b)$. The converse is false; a smaller logical timestamp does not establish causation.

Consensus is agreement on a value or ordered log under a stated failure model. A majority’s overlap with another majority is a useful safety ingredient, but it is not a complete consensus algorithm. Terms, voting rules, log restrictions, persistence, commit rules, and recovery all matter. Raft is an appropriate continuation because its paper explains these mechanisms and their relationship to safety. The lab here does not implement Raft and does not turn a single SQLite database into a fault-tolerant distributed cluster. [RAFT]

F. A precise CAP thought experiment#

Consider an atomic read/write register replicated across two groups separated by a partition that can prevent messages indefinitely. A write of a new value completes in the first group. A later read reaches the second group. That group cannot distinguish this history from one in which a different write completed on the other side. If it must always eventually return a register value without communication, some history will receive the wrong value. If it waits indefinitely for the missing information, it loses the required availability.

Thus the theorem’s conflict concerns linearizable register behavior and a response to every request at nonfailed nodes in a model allowing partitions. It is not a claim that every application chooses two features forever or that an error response automatically provides useful register availability. Normal operation may provide both fast responses and strong semantics; the difficult choice appears in failure histories allowed by the model. Different operations in one product can choose different policies. A public profile picture may tolerate staleness while a scarce-item reservation must not oversell. Gilbert and Lynch’s Perspectives on the CAP Theorem gives the assumptions and indistinguishability argument used here. [CAP]

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C13#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C13.05: an explicit simulation; not durable distributed storage."""
class Ledger:
    def __init__(self, balance: int):
        self.balance = balance
        self.results: dict[str, tuple[int, int]] = {}

    def debit(self, key: str, amount: int, lose_reply: bool = False) -> int:
        if not key or type(amount) is not int or amount <= 0:
            raise ValueError("key and positive integer amount required")
        if key in self.results:
            previous_amount, result = self.results[key]
            if previous_amount != amount:
                raise ValueError("idempotency key reused with a new request")
            return result
        if amount > self.balance:
            raise ValueError("insufficient balance")
        self.balance -= amount
        self.results[key] = (amount, self.balance)
        if lose_reply:
            raise TimeoutError("simulated lost reply AFTER commit")
        return self.balance

if __name__ == "__main__":
    ledger = Ledger(10)
    try:
        ledger.debit("request-1", 3, lose_reply=True)
    except TimeoutError:
        pass
    print(ledger.debit("request-1", 3), ledger.balance)

I. Retention and readiness#

Retrieve the C11 transfer transaction and C12 transport/application distinction. Advance when you can place the commit point on a failure timeline and say what a retry can safely assume. Continue with the local transactional service J03; read a consensus paper only after you can restate its failure model and safety claim.