Two machines. Each holds a number called count, starting at zero. A client wants to increment the counter, and to keep the two machines identical it sends the increment to both. Do that five times and both should read 5. Here’s the whole thing:

class Node:
    def __init__(self, name): self.name = name; self.count = 0
    def increment(self): self.count += 1

A = Node("A"); B = Node("B")
for i in range(1, 6):
    A.increment()
    B.increment()      # ... unless the message never arrives

Now the network does the one thing networks do. On the third increment, the message to B is lost, not corrupted, not delayed, just gone, the way a real packet gets gone. I ran exactly that:

$ python3 hook.py
  increment #1: A=1 B=1
  increment #2: A=2 B=2
  increment #3: message to B DROPPED
  increment #4: A=4 B=3
  increment #5: A=5 B=4

final:  A=5  B=4

A says 5. B says 4. The client sent five increments and there’s no honest answer to “what is the count,” because the two machines that are supposed to be the same machine now disagree, and nothing in this design will ever fix it. There’s no line of code that reconciles them, no moment where B notices it’s behind. The disagreement is permanent, it came from a single lost packet, and every distributed system you’ve ever used exists to prevent exactly this.

The first repair breaks when a reply disappears. The second breaks when two clocks disagree. The third survives a partition but forgets everything when the process dies. I kept the counter and changed one mechanism at a time until three child processes could be killed, restarted from disk, and forced to reconcile a conflicting log. The network experiment in two machines talking to each other established the assumption used here: a sender can wait without knowing whether its request vanished, its reply vanished, or the receiver is merely slow.

The channel is the enemy

Before reaching for a fix, it’s worth being precise about what broke, because the instinct, “just make delivery reliable”, is a trap, and seeing why is half the subject.

The client sent a message. It vanished. The client has no way to tell the difference between the message was lost, the message arrived but B’s reply was lost, and B is just slow and the reply is still coming. From the sender’s side those three are identical: silence. This is the fundamental predicament, and it has a formal name, the two generals problem, but you don’t need the formalism, you need the feeling of it. You cannot build guaranteed agreement on top of a channel that can drop any message, because the acknowledgment that would confirm agreement can itself be dropped, and so can the acknowledgment of that. There’s no bottom to it. TCP doesn’t escape this (it just retries and eventually gives up); nothing escapes it. The channel is unreliable, full stop, and every technique below is a way to build something trustworthy on top of something that isn’t.

The two generals problem is worth sitting inside for a second, because if you understand it viscerally you understand why the rest of the post exists. Two generals on opposite hills need to attack at the same dawn, and the only way to coordinate is a messenger who runs through the valley where he might be captured. General A sends “attack at dawn.” Did it arrive? A doesn’t know until B sends back “agreed.” Did that arrive? Now B doesn’t know if A got the confirmation, so B waits for A to confirm the confirmation, and A waits to confirm that, and you can chase this forever and never reach a point where both generals know the other is committed. It is not a hard problem in the sense of needing a clever algorithm. It is provably impossible: no finite exchange of messages over a lossy channel can make two parties certain they agree. Everything practical is a way of getting probably agreed, or agreed unless the whole thing is down, and being honest about the gap.

So the honest starting move is not “make the channel reliable.” It’s “assume the channel loses things, and design so that agreement survives anyway.” Watch how far the naive fixes get.

Fix one: just resend. Now we count too much.

If a message might be lost, resend it until you get an acknowledgment. The client sends “increment,” waits for an ACK, and retries if none comes. Reasonable. Now drop the ACK instead of the request, the node got the increment, applied it, and its “done!” reply is what vanished:

$ python3 retry.py
  attempt 1: node applied (count=1), ACK DROPPED -> client will retry
  attempt 2: node applied (count=2), ACK received -> client done

client asked for ONE increment. node.count = 2 (applied 2 times).

The client asked for one increment. The counter went up by two. The node did nothing wrong, it received two messages and applied two increments, but from the client’s side, the retry that was supposed to recover a lost message instead duplicated a delivered one. Retrying turned “maybe zero” into “maybe two.”

One double-count in one transcript is an anecdote, not a measurement, and I didn’t yet have a feel for how bad the damage gets. So I put a lossy channel between a client and a single node, gave the client exactly twenty thousand increments to perform, and let it run each of the three strategies in turn. The channel drops a given packet, request or acknowledgment, with a fixed probability, and I counted how far the node’s final count landed from the honest 20000:

$ python3 retry_montecarlo.py
drop=0.1:  each client asks for exactly 20000 increments
  at_most_once  : final counter off by  -2039  (-10.20%)
  at_least_once : final counter off by +  2261  (+11.30%)
  idempotent    : final counter off by +     0  (+0.00%)

drop=0.3:  each client asks for exactly 20000 increments
  at_most_once  : final counter off by  -6010  (-30.05%)
  at_least_once : final counter off by +  8549  (+42.74%)
  idempotent    : final counter off by +     0  (+0.00%)

At-most-once (send once, never retry) undercounts by almost exactly the drop rate, which makes sense: if you never retry, the only way to lose an increment is for the very first request to vanish, and that happens at the drop probability. Ten percent drop, ten percent loss. Clean.

At-least-once is where I got a number I hadn’t predicted. I expected the overcount to be about the drop rate too, symmetric with the undercount. It wasn’t. At ten percent drop the counter runs eleven percent hot, close enough, but at thirty percent drop it’s forty-three percent too high, and forty-three is a lot bigger than thirty. I stared at that before it clicked: every retry is itself a fresh roll of the dice, and a retry whose request lands but whose ACK drops gets applied and then retried again. The overcount isn’t the drop rate, it’s the drop rate compounded over however many round trips it takes to finally get an ACK back, and the worse the channel, the more times each operation gets re-applied before the client hears “done.” Loss doesn’t just cost you the occasional duplicate. On a bad channel it snowballs.

The larger overcount has a short derivation. Let p be the probability that an acknowledgement is lost after an application. The first application always happens in this simplified branch. A fraction p require a second application, a fraction p * p require a third, and the expected applications are

1 + p + p^2 + p^3 + ... = 1 / (1 - p)

At p = 0.3, that is 1 / 0.7 = 1.4286 applications for one requested effect, or 42.86% excess. The run reported 42.74%. The difference is finite sampling. The channel in the program can also drop requests, which adds waiting but not applications, so it does not change this conditional geometric series.

The idempotent result was zero in these finite runs. The program caps an operation at fifty attempts, so zero is an observation, not a proof that an arbitrarily bad channel eventually delivers. With independent packet loss of 0.3, exhausting all fifty attempts is too unlikely to appear in twenty thousand operations. A permanent partition would exhaust every attempt. Deduplication prevents a delivered retry from applying twice; it cannot make an unreachable node answer.

The three labels describe distinct contracts. At-most-once sends once, so it avoids duplicates by accepting omission. At-least-once retries, so it avoids omission while accepting duplicates. An exactly-once effect needs a stable operation identity and an atomic boundary around deduplication and the state mutation. A Python set in memory demonstrates the identity rule. It does not yet provide that atomic boundary, because a crash can erase the set or occur between changing the counter and recording the identifier.

But dedup fixes double-counting, not disagreement. Even if every message arrives exactly once, two machines can still end up different, because of when things arrive.

Fix two: agree on an order, without a clock

Suppose two clients increment at the “same time,” and their messages reach machine A in one order and machine B in the other. For a counter it doesn’t matter, addition commutes, +1 then +1 is the same as +1 then +1. But replace increment with “set balance to 100” and “add 50 interest,” and order is the difference between 150 and 100. The moment operations don’t commute, every replica has to apply them in the same order or diverge, and now I need a way to agree on order across machines.

The obvious idea, timestamp every operation with the wall clock and sort, fails on the rock that there is no shared wall clock. Every machine’s clock drifts; two events a microsecond apart on different machines can carry timestamps that disagree about which came first. Physical time is not a reliable order in a distributed system, and building on it is how you get bugs that only appear when two servers’ clocks slip.

“Not reliable” was doing too much work in that sentence, so I tested a mathematical model rather than a pair of synchronized machines. Machine A sends a message. Machine B receives it. The receive cannot precede the send. The program draws each clock offset independently from a uniform interval and draws transit time uniformly between zero and half a millisecond. It then stamps the two events with those synthetic clocks and counts inversions:

$ python3 clockskew.py
clock skew +/-    1ms, transit up to 0.5ms  (over 200000 message deliveries):
    wall-clock order inverts causality:  36.32% of the time
    Lamport order inverts causality:      0.00% of the time

clock skew +/-    5ms, transit up to 0.5ms  (over 200000 message deliveries):
    wall-clock order inverts causality:  46.92% of the time
    Lamport order inverts causality:      0.00% of the time

clock skew +/-   50ms, transit up to 0.5ms  (over 200000 message deliveries):
    wall-clock order inverts causality:  49.72% of the time

With offsets drawn from plus or minus one millisecond, the model inverted 36.32 percent of its causal pairs. That is not a measurement of NTP, a production clock service, or any particular machine. It says something narrower and useful: when uncertainty in the difference between two clocks is large compared with the physical time between two events, sorting the raw timestamps cannot reliably recover their causal order. As the synthetic offset range dwarfs the transit range, the inversion rate approaches one half. Changing the offset distribution changes the percentages but not the missing information.

Leslie Lamport’s 1978 paper on logical clocks asks for a clock condition: if event X happened before event Y in the causal relation, then X’s logical timestamp must be less than Y’s. A plain counter per process can satisfy that one-way implication. Increment it on a local event. Attach it to a sent message. On receipt, set it to max(mine, theirs) + 1. Receiving a message then advances the receiver beyond the send timestamp by construction. The synthetic run reports no Lamport inversions because the algorithm makes one impossible, not because a random sample happened to miss one. I ran the concrete three-process event sequence:

$ python3 lamport.py
  Lamport ts | node | event
       1     |  A   | a1
       1     |  B   | b1
       1     |  C   | c1
       2     |  A   | send:m1->B
       3     |  B   | recv:m1
       4     |  B   | send:m2->C
       5     |  C   | recv:m2

Follow the causal chain: A does local work at 1 and sends at 2. B receives at 3, sends at 4, and C receives at 5. No process compared physical clocks. The converse does not hold. L(X) < L(Y) does not prove that X caused Y, and equal scalar timestamps do not prove concurrency. These particular three local events have no causal edges between them because of how the program was constructed, not merely because all three show 1. Appending a process identifier as a tie breaker produces a deterministic total order. That total order is useful, but it contains invented order between events that were not causally related.

A Lamport clock plus a tie breaker can order every pair, but cannot answer whether an observed pair is causally related or concurrent. Vector clocks preserve enough componentwise information to answer that question for the processes they represent. The distinction becomes necessary when both sides of a partition accept writes.

So now I can dedup operations and order them consistently. Two machines given the same set of operations will agree. But I’ve been assuming both machines stay alive. The whole reason to have two was so that one could die.

Fix three: replicate, and rediscover the disagreement

Put the counter on three machines so it survives one of them failing. Call them replicas, identical copies of the same state. Immediately the original problem comes back wearing a bigger coat: if any replica can accept a write, and a write reaches some replicas but not others (because, remember, the channel drops things), the replicas diverge. That’s the opening hook again, just with three machines instead of two. Replication doesn’t solve disagreement; it’s where disagreement gets dangerous, because now the system is supposed to have multiple copies and somebody has to define which copy is right.

The wrong answer is “all of them”, require every replica to accept a write before it counts. That’s safe but fragile: one slow or dead replica freezes the whole system, which defeats the point of replicating for fault tolerance. The other wrong answer is “any of them”, let each replica take writes independently and hope they reconcile later, which is the hook’s permanent divergence by design.

The answer that works is most of them.

Quorums: most is enough, and most always overlaps

Here’s the idea that makes replication safe, and it’s pure counting. With three replicas, require a write to reach a majority, any two, before it’s acknowledged, and require a read to consult a majority too. Store a version number with each value. The reader takes the highest version it sees. I ran it:

$ python3 quorum.py
N=3. write value=42 version=1 to a WRITE quorum of W=2 replicas {0,1}. replica 2 misses it.
  replica states: ['v42@ver1', 'v42@ver1', 'v0@ver0']
  read R=2 from [1, 2] -> 42 (ver 1)   [overlaps the write? yes]
  read R=2 from [2, 0] -> 42 (ver 1)   [overlaps the write? yes]
  read R=2 from [0, 1] -> 42 (ver 1)   [overlaps the write? yes]

Replica 2 completely missed the write. It still holds the old value. And yet every possible two-replica read returns the new value, because every pair of replicas that could form a read quorum shares at least one member with the pair that formed the write quorum. Two sets of size 2 drawn from a pool of 3 cannot be disjoint, they must overlap in at least one replica, and that one replica carries the new version forward. The reader consults two, one of them has version 1, the higher version wins, done. The stale replica is harmless because it can never be the only replica a read talks to.

That overlap isn’t luck, it’s arithmetic, and the arithmetic is a single inequality: if the write quorum size W plus the read quorum size R is greater than the total N, the two quorums must intersect. Here W + R = 2 + 2 = 4 > 3 = N. Break that inequality and safety evaporates:

  W=1,R=1: write to {0}, read from {2} -> 0 (ver 0). W+R=2 <= N=3: stale read. lost the update.

Write to one replica, read from a different one, and the reader never sees the write. W + R = 2, which is not greater than 3, so the quorums can miss each other, and this one did. In this toy there is one completed writer, monotonically assigned versions, no concurrent write, and a reader that takes the maximum version. Under those assumptions, W + R > N guarantees that this read intersects this write. It does not manufacture a safe version generator, order concurrent writes, perform read repair, or prove that a complete service is linearizable. Those requirements will reappear when the value becomes a log.

For a group in which every member votes, N = 2f + 1 members and a quorum of f + 1 can continue after f crash failures, provided the survivors can communicate. Three voting members tolerate one unavailable member. Five tolerate two. Four voting members still tolerate only one because its majority is three. That fourth voter does not increase this particular failure budget. It may provide read capacity, geographic placement, or a migration step, and systems can add nonvoting learners or witnesses for other purposes. The narrow result is about majority voting capacity, not a rule that every even deployment is worse.

Two configurations, one safe and one broken, still left me taking the inequality partly on faith, and I don’t like taking arithmetic on faith when I can just measure it. So I swept every possible (W, R) pair for a three-replica system and a five-replica one: write version 1 to W random replicas, read from R random ones, take the highest version, and count how often the read missed the write, a hundred thousand trials per cell.

$ python3 quorum_sweep.py
N=3: stale-read rate by (W,R).  bold zero == W+R>N (guaranteed overlap)
      R=1      R=2      R=3
  W=1   0.664    0.334    0.000*
  W=2   0.332    0.000*   0.000*
  W=3   0.000*   0.000*   0.000*

N=5: stale-read rate by (W,R).  bold zero == W+R>N (guaranteed overlap)
      R=1      R=2      R=3      R=4      R=5
  W=1   0.800    0.597    0.401    0.200    0.000*
  W=2   0.603    0.299    0.101    0.000*   0.000*
  W=3   0.400    0.101    0.000*   0.000*   0.000*
  W=4   0.202    0.000*   0.000*   0.000*   0.000*
  W=5   0.000*   0.000*   0.000*   0.000*   0.000*

The zeros form a staircase whose edge is W + R = N. Every cell above that line has zero misses because two sets of those sizes cannot be disjoint. The zero is derived, not inferred from one hundred thousand trials. The positive cells are properties of this random selection model. An implementation that routes requests by locality, load, or failure domain can produce different rates while retaining the same possibility of disjoint quorums.

And the positive numbers aren’t noise, they’re combinatorics I can check by hand, which is the moment I trust a simulation instead of suspecting it. Take N=5, W=2, R=2: it reads stale 29.9% of the time. The exact odds that two randomly chosen read replicas both avoid the two written replicas is C(3,2)/C(5,2) = 3/10 = 0.300. The measurement landed on 0.299. When a number I can compute two completely different ways agrees to the third decimal, I stop worrying that I’ve fooled myself, and the whole W+R>N story stops being a slogan and becomes a thing I watched happen.

The sweep says which configurations guarantee overlap in its single value model. It says nothing about the latency of obtaining those responses. My first latency program hid an important policy choice: it contacted exactly R replicas and waited for all R. Another client can contact all N replicas and return after the fastest R, spending more requests to avoid slow responders. I compared both policies with a synthetic response distribution. A response is uniform from 2 to 8 milliseconds with probability 0.9 and uniform from 30 to 120 milliseconds otherwise. These are assumed distributions, not production measurements:

synthetic N=5 response distribution: 90% uniform 2..8ms, 10% uniform 30..120ms
chosen R contacts exactly R; fanout N contacts 5 and waits for the fastest R
       chosen R policy                 fanout N policy
R=1: mean= 12.05 p50=  5.34 p99=110.92 | mean=  3.11 p50=  2.87 p99=  5.99
R=2: mean= 19.37 p50=  6.72 p99=115.44 | mean=  4.25 p50=  4.10 p99=  7.18
R=3: mean= 25.42 p50=  7.29 p99=116.86 | mean=  5.70 p50=  5.33 p99=  7.95
R=4: mean= 31.06 p50=  7.60 p99=117.81 | mean= 10.91 p50=  6.58 p99= 90.94
R=5: mean= 36.32 p50=  7.80 p99=118.17 | mean= 35.88 p50=  7.80 p99=118.21

The chosen policy reproduces the earlier table: increasing R raises the chance that at least one chosen replica comes from the slow component. Its mean rises from 12.05 to 36.32 milliseconds. Fanout changes the order statistic. For R = 1, any one of five fast responses is enough, so the synthetic p99 falls from 110.92 to 5.99 milliseconds. For R = 3, a majority of the full group must be slow before a slow response controls completion, and p99 is still 7.95 milliseconds. That latency is purchased with five requests instead of three and with work that may continue after the client has enough replies. Quorum size and fanout policy are separate variables. The original experiment had accidentally fused them.

Quorums make a single value safe. But a counter isn’t a single value, it’s a sequence of operations, and “increment” applied to a stale replica gives a different answer than “increment” applied to a current one. To replicate a counter, the replicas don’t need to agree on the current value; they need to agree on the ordered list of operations, and then each replays it. Agreeing on an ordered, replicated list of operations, in the face of a lossy network and dying machines, is the problem called consensus, and it’s the summit of this post.

the process died and took the promise with it

My first replicated log was an object graph in one Python process. It had three Node instances, a set of disconnected pairs, and a function that copied one list into another. Calling those objects three machines made the transcript sound stronger than the experiment. Killing the Python process erased the current term, every vote, every log entry, and the evidence that a client operation had already been applied. The model illustrated majority commit, but it could not test recovery from a process failure.

I replaced it with three child processes. The parent still chooses the election and message schedule so every failure is repeatable. Communication uses local pipes rather than sockets. Each child owns a separate state file and implements only five requests: start an election, vote, append a local entry, accept an AppendEntries request, and advance the commit index. This remains a controlled protocol probe, not a complete Raft implementation.

The state that outlives a process is small:

{
  "term": 2,
  "voted_for": "n1",
  "log": [
    {"term": 1, "kind": "increment", "client": "c", "sequence": 1, "result": 1}
  ],
  "commit": 1
}

term rejects messages from an older leadership epoch. voted_for prevents one process from granting two votes in the same term. Each log entry carries the term in which its leader created it. commit divides the prefix that may affect the counter from the suffix that remains provisional. The client and sequence pair identifies a logical operation. The result is stored with the operation so a retry can receive the same answer rather than recomputing an answer from later state.

Before a child replies to a mutation, it writes a new JSON file, calls fsync on that file, replaces the old path, and calls fsync on the containing directory:

def atomic_store(path, state):
    tmp = path.with_suffix(".tmp")
    with tmp.open("w", encoding="utf-8") as f:
        json.dump(state, f, sort_keys=True, separators=(",", ":"))
        f.flush()
        os.fsync(f.fileno())
    os.replace(tmp, path)
    directory = os.open(path.parent, os.O_RDONLY)
    try:
        os.fsync(directory)
    finally:
        os.close(directory)

The file fsync asks the operating system to make the new file contents durable. The rename changes which complete file the stable name refers to. The directory fsync asks for that name change to become durable too. A successful return is still not a proof against every storage failure. This run did not cut power, bypass a lying device cache, corrupt sectors, or test a filesystem other than the current machine’s. It did establish a much harder boundary than an in-memory list: SIGKILL cannot run cleanup handlers, and a fresh process must reconstruct its answer from bytes written before death.

This JSON rewrite is not a production write ahead log. A service would append records with checksums, batch syncs, recover a torn tail, compact old entries into snapshots, and bound disk growth. Rewriting the complete state gives this experiment a small inspectable persistence path. It also makes the point that durability is part of the consensus state, not a storage detail that can be added after the election code works. If a process grants a vote and replies before voted_for is durable, it can die, forget the vote, restart, and grant another candidate a second vote in the same term. The Byzantine double vote at the end of this investigation can be created accidentally by missing persistence.

The extended Raft paper distinguishes state that must be updated on stable storage before responding, including the current term, the vote, and the log. My probe also persists its commit index to keep restart behavior explicit. It borrows the paper’s vote freshness and log prefix checks. It does not inherit the paper’s safety proof merely by sharing those lines.

entry two arrived before entry one

n0 wins term 1. The parent sends the first client increment to n0 and n1, then marks it committed. It deliberately leaves n2 empty. n0 appends sequence 2 and the parent delivers only that second entry to n2, claiming that entry 1 is its predecessor. n2 checks the predecessor index and term before touching its log:

if previous_index > len(state["log"]):
    reply(False, reason="missing predecessor")
elif previous_index and state["log"][previous_index - 1]["term"] != previous_term:
    reply(False, reason="predecessor term")

The first negative control appears in the transcript:

phase 1: elect n0 and commit client c sequences 1 and 2
  deliver entry 2 to empty n2 before entry 1: accepted=False reason=missing predecessor
  duplicate full-prefix delivery left n2 log length at 2

An ordered log cannot contain a hole. Sequence 2 is a valid command with a valid term, but accepting it at index 2 without knowing index 1 would let two replicas interpret the same index sequence differently. The rejection is not about packet order itself. Networks may reorder packets. It is about refusing to turn reordered delivery into reordered state.

The parent then sends the complete prefix containing entries 1 and 2. n2 accepts it. The parent sends the same prefix again. The log stays at length 2 because the child compares an existing entry with the offered entry and appends only entries not already present:

for entry in entries:
    if insert_at < len(log):
        if log[insert_at] != entry:
            log = log[:insert_at]
            log.append(entry)
    else:
        log.append(entry)
    insert_at += 1

That loop is doing two different jobs. An identical entry is a duplicate delivery and changes nothing. A different entry at the same index is a conflict, so the old entry and everything after it are removed before the new suffix is appended. Duplicate suppression at the transport boundary and conflict repair at the log boundary therefore share one comparison, but they represent different events.

Sending the complete prefix on every repair is intentionally inefficient. Raft leaders track a next index and matching index for each follower, back up to the first matching predecessor, and send only the missing suffix. This probe sends a whole six-entry log because bandwidth is not the variable being tested. The safety relevant check is that a follower accepts a suffix only after identifying the same prefix.

the reply vanished after the commit

The opening retry failed because the counter mutation and the deduplication record existed only in unrelated memory. The durable entry puts the client identity, sequence number, operation, and result in one replicated record. Before appending, the leader scans only the committed prefix for the same client and sequence:

for entry in state["log"][:state["commit"]]:
    if entry["client"] == client and entry["sequence"] == sequence:
        return entry["result"]

The parent asks for client c, sequence 3. n0 appends result 3, n1 accepts the prefix, and the entry commits on two processes. The experiment then discards the client response. It submits the same client and sequence again:

phase 2: commit sequence 3, lose the client response, then retry
  retry returned result=3; log length stayed 3

The retry obtains the stored result. It does not append another increment. The stable identity makes a request safe to repeat, while the stored result makes the repeated response consistent with the first execution. If the protocol stored only a set of identifiers, a retry after later increments could be recognized as old without being able to reconstruct what the original call returned.

Three writes must move together conceptually: the operation, its deduplication identity, and its result. If the counter is updated in one database transaction and the dedup table in another, a crash between them revives the original ambiguity. Recording the identifier first can suppress an effect that never happened. Applying the effect first can duplicate it after restart. The log entry avoids that split because applying the committed prefix derives both the counter and the completed operation results from the same ordered record.

There remains a second boundary between replication and response. A leader must not tell the client that sequence 3 succeeded and then lose the only durable copy. In this probe the leader returns only after a majority has persisted the entry and the local commit marker has been persisted. The client response is allowed to vanish after that point. Retrying against a later leader will find the operation in the committed history.

The experiment does not solve unbounded deduplication. Six identities remain forever. A production protocol can use monotonically increasing per-client sequence numbers and retain the last result, expire sessions under an explicit retry bound, or include deduplication state in snapshots. Each choice creates a contract. A client that retries after its session expired can no longer demand exactly one effect. Calling the feature exactly once without stating that lifetime hides the most operationally important limit.

the promise waited for storage

Persisting before replying changes the latency path. An increment is no longer a Python integer addition followed by a network acknowledgement. The leader writes the entry, at least one follower writes it for a three member majority, the leader learns that the majority write completed, and only then can the operation become an acknowledged promise. CPU time for count += 1 is irrelevant if the critical path waits on storage and communication.

The waits are not necessarily a simple sum. A leader can send replication requests to both followers concurrently. If its own local persistence takes L seconds and follower response times including persistence are F1 and F2, a simplified three member commit time after receipt is approximately

max(L, min(F1, F2))

The leader needs its own durable copy and one of the two follower copies. It waits for the faster follower, not both. This expression omits serialization, queueing, network send time already included in F, applying the state machine, and the client response. Its value is the shape: majority replication creates an order statistic on durable acknowledgements.

The process probe cannot measure that path. All children write to the same local storage stack, communicate through pipes, and contend on one machine. Treating its wall time as a distributed commit latency would invent a hardware result. A networked run would need per-node storage, clocks suitable for interval measurement, repeated samples, batch size, sync policy, filesystem, device model, and failure injection that confirms replies do not move before durability.

Storage latency also creates pressure to batch. Suppose one durable flush takes exactly 1 millisecond and every other cost is zero. Flushing one operation at a time caps that artificial leader at

1 operation / 0.001 seconds = 1,000 operations per second

Putting sixteen log entries behind the same flush changes the derived ceiling to

16 operations / 0.001 seconds = 16,000 operations per second

Those are dimensional predictions from an assumed latency, not measurements. A real device may combine writes, cache them, vary by queue depth, or make fsync much slower. The calculation explains why replicated logs use group commit: the expensive durability boundary is shared by several operations.

The batch creates a queueing decision. Waiting to collect sixteen requests improves flush efficiency when traffic is high and adds avoidable delay when traffic is low. A service can close a batch when it reaches a size limit or when a short timer expires. The first request in the batch waits longest. The last may arrive just before the flush. Throughput, median latency, and tail latency therefore respond differently to the same batching policy.

Failure semantics stay per operation even when persistence is batched. If a batch of sixteen entries reaches a majority and the leader dies before sending responses, all sixteen clients may retry operations that are already committed. Every identity and stored result must survive. If only nine entries were replicated before failure, the protocol cannot infer that the first nine client calls were the ones whose callers received replies unless response order is tied to commit order. Batching changes amortization, not the point after which a reply is safe.

Slow followers introduce a second queue. A leader can commit using the fastest majority while one follower falls behind. Its missing suffix grows until it catches up or needs a snapshot. That lag does not delay each foreground write, but it reduces the failure margin: if the leader then dies, the election must choose a candidate whose log still contains committed history. The freshness rule in the next failure sequence is what keeps the fast path from promoting a stale replica after using it as spare capacity.

the old leader returned with another history

n0 now has three committed entries. The parent isolates it by declining to deliver replication messages to either follower. The client submits sequence 4. n0 persists a term 1 entry at index 4, but one copy is not a majority, so it does not advance its commit index and no successful client response is produced:

phase 3: isolate n0, append sequence 4 without a quorum, then SIGKILL it
  n0 has uncommitted term-1 entry at index 4; no response is acknowledged
  n0 process exited from SIGKILL

The process is killed with SIGKILL. It cannot flush a Python buffer during shutdown or serialize one last friendly snapshot. Its state file already contains commit index 3 and a log of length 4. That difference is the durable representation of uncertainty: the first three entries may affect the state machine; the fourth may not.

n1 and n2 can communicate. n1 begins term 2, votes for itself, and asks n2. The request contains n1’s last log term and last log index. n2 grants only if it has not voted for someone else in term 2 and the candidate’s log position is at least as recent as its own:

candidate_position = (candidate_last_term, candidate_last_index)
local_position = (local_last_term, local_last_index)
grant = same_term and can_vote and candidate_position >= local_position

Comparing the last term before the last index matters. A shorter log whose last entry came from a later term can contain committed history that a longer stale log lacks. A candidate with an out of date log must not win merely because it has many provisional entries. The Raft election restriction uses this freshness check so every later leader contains entries already committed in earlier terms.

n1 and n2 commit a new sequence 4 in term 2 at index 4, then sequence 5 at index 5. The client receives the result for sequence 5. The parent immediately kills n1:

phase 4: elect n1 with n2, retry sequence 4, then commit sequence 5
  n1 and n2 committed results 4 and 5 in term 2
  n1 was killed after its client response for sequence 5

This death is placed after an acknowledged operation because that is the promise the system must preserve. A failure before acknowledgement may leave an operation committed or absent, which is why the client retries with the same identity. A failure after acknowledgement must never make the operation disappear from future successful reads. n2 has the committed term 2 entries on disk, so it can carry that promise into the next term.

The parent restarts n0. Its file still contains the conflicting term 1 sequence 4 at index 4. n2 has a term 2 sequence 4 at the same index plus sequence 5. n2 starts term 3. Its last position (term 2, index 5) is newer than n0’s (term 1, index 4), so n0 grants the vote. n2 appends sequence 6 and sends its prefix. The first three entries match. Index 4 does not:

stale n0: [1, 1, 1, 1]       commit=3
leader n2: [1, 1, 1, 2, 2, 3] commit=6
                         ^
                  first conflicting term

n0 truncates from the conflict and installs the leader’s term 2 and term 3 suffix. The provisional entry from its old leadership disappears. It is safe to remove because n0 never had a majority for it and never acknowledged it. The client retried sequence 4 against the term 2 leader, so the intended effect still exists exactly once under the same identity.

phase 5: elect n2, commit sequence 6, restart stale n0, and repair it
  after the old term-1 suffix is replaced:
  n0: term=3 log_terms=[1, 1, 1, 2, 2, 3] commit=6 count=6 dedup=6
  n2: term=3 log_terms=[1, 1, 1, 2, 2, 3] commit=6 count=6 dedup=6

n1 is then restarted and caught up. Finally the parent kills and restarts each process, one at a time, without changing its file. Every recovered process reports the same committed log, count, and number of remembered operation identities:

phase 6: restart every node from disk
  recovered durable state:
  n0: term=3 log_terms=[1, 1, 1, 2, 2, 3] commit=6 count=6 dedup=6
  n1: term=3 log_terms=[1, 1, 1, 2, 2, 3] commit=6 count=6 dedup=6
  n2: term=3 log_terms=[1, 1, 1, 2, 2, 3] commit=6 count=6 dedup=6
  assertion: all committed logs, counts, and dedup records agree

This is directly measured process recovery on the current machine. Message loss, reordering, and duplication are scheduled by the parent rather than produced by a real socket network. Elections are invoked by the parent. There are no autonomous heartbeats, no concurrent candidates, no membership changes, no snapshots, no batching, no read protocol, and no proof over all possible schedules. The child code implements enough persistent state and prefix repair to expose why the earlier in-memory transcript was insufficient. It should not be deployed or described as Raft.

matching replicas can still give a wrong answer

All three processes ending at count 6 proves convergence for one schedule. It does not define what a client was allowed to observe while operations overlapped. A service could keep identical logs and still answer a read from an old committed prefix after a newer increment had already returned. Replica agreement and client-visible correctness are related, but they are not the same property.

For this counter, I want each operation to appear to take effect at one instant somewhere between its invocation and its response. If increment A returned before read B began, B must observe A. Operations whose intervals overlap may be ordered either way if their return values remain legal. This property is linearizability, as defined by Herlihy and Wing in Linearizability: A Correctness Condition for Concurrent Objects.

I wrote a brute force checker for small histories. It records the start time, finish time, operation kind, and returned value. Before placing an operation into a candidate sequential order, the checker requires every operation that finished before this one started to have been placed. It then executes the candidate against a plain integer counter and rejects a return value that the sequential counter could not produce:

expected = count + 1 if operation.kind == "increment" else count
if operation.result != expected:
    continue

The first history contains overlap:

$ python3 linearizability_probe.py
overlapping history:
  increment A interval=[0,5] returned=1
  increment B interval=[2,8] returned=2
  read C      interval=[7,10] returned=2
  increment D interval=[9,12] returned=3
  linearization: increment A -> increment B -> read C -> increment D

Increment B overlaps both A and read C. The checker can place it after A and before C, which explains every return value while respecting the required order between nonoverlapping calls. Increment D overlaps the end of C, so placing it after the read is legal.

The negative control ends an increment before a stale read begins:

stale-read control:
  increment A interval=[0,2] returned=1
  read B      interval=[3,4] returned=0
  linearization: NONE

There is no legal place for the read. Real time forces the increment before it, and a sequential counter after that increment is 1. A returned 0 cannot be repaired by choosing a different order. The checker’s failure is useful because it shows what a consistency test has to falsify, not merely what a successful replication transcript looks like.

The checker explores every legal ordering and is exponential in the number of overlapping operations. It is appropriate for these four calls, not a long production trace. The durable process probe also did not expose a read API or record invocation intervals, so I cannot claim that run was checked for linearizability. A fuller service would need a leader read protocol, such as a quorum confirmation or a valid leader lease with carefully stated clock assumptions, plus histories captured at the client boundary.

the timeout I had supplied by hand

The parent calls elect(n1) and later elect(n2). No child notices a missing heartbeat and starts an election. My old election simulation tried to fill that gap and was wrong in two ways. It modelled three followers after the leader of a three member cluster died, which creates one process too many. It also treated any pair of nearby timeouts as proof that an election failed, even in larger clusters where another voter could give one candidate a majority.

I replaced it with a narrow case that can be derived. A three member cluster loses its leader, leaving two followers. Each independently chooses a timeout from a window of width W. A vote request takes a fixed D = 10 milliseconds one way. If the two timeouts differ by at most D, both followers become candidates and vote for themselves before either sees the other’s request. With the third member unavailable, the term splits one vote to one.

Two random timeouts are two coordinates in a W by W square. A collision occupies the diagonal band where their distance is at most D. The two noncollision triangles have total area (W - D)^2, for D <= W. The collision probability is therefore

P(collision) = 1 - (W - D)^2 / W^2
             = 1 - (1 - D/W)^2

If every new term draws independent timeouts, a collision-free term has probability 1 - P(collision), and its expected round number is the reciprocal of that success probability. The simulation and derivation agree:

$ python3 election_splitvote.py
three-node model: leader dead, two followers, fixed one-way delay D=10ms
W is the width of the independent randomized timeout window
      W   measured collision   derived collision   derived rounds
      0ms       100.000%             100.000%          unbounded
      5ms       100.000%             100.000%          unbounded
     10ms       100.000%             100.000%          unbounded
     25ms        63.929%              64.000%          2.778
     50ms        35.955%              36.000%          1.562
    100ms        19.025%              19.000%          1.235
    150ms        12.917%              12.889%          1.148
    300ms         6.611%               6.556%          1.070

The percentages describe this synthetic two-candidate model. Ten milliseconds is an assumption, not a measured network delay. unbounded means the model has zero probability of a collision-free round when W <= D. It does not prove that an actual Raft implementation can never elect a leader under those timings. Real messages have variable delay, terms advance at different times, failures recover, and implementations reset timers in response to protocol events. The model isolates only the reason independent randomized timeouts reduce one kind of repeated split.

Raft uses randomized election timeouts to make split votes rare and retries with a new term after an unsuccessful election. Timing affects availability, while the protocol’s term, vote, and log restrictions provide safety. That separation matters. A terrible timeout choice can leave a safe cluster without a leader. It should not let two different committed commands occupy the same log index.

The thing you had to give up

The isolated n0 persisted sequence 4 but did not acknowledge it. A client that could reach only n0 received no successful increment. That refusal was the desired behavior for this counter, but saying “CAP means choose consistency or availability” compresses the theorem until its important nouns lose their definitions.

The result proved by Seth Gilbert and Nancy Lynch in Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services uses atomic consistency. This is the same client-visible condition the history checker called linearizability: every operation appears at one point between invocation and response, and nonoverlapping operations preserve real-time order. It does not mean that all replicas hold identical bytes at every instant.

Availability in that model means every request received by a nonfailing node eventually receives a response. It does not mean five nines, low latency, or that a majority remains useful. A node that waits forever because it cannot hear the other partition violates this definition even if waiting is the safest product behavior.

Partition tolerance means the algorithm must continue to satisfy its advertised property while the network may lose an arbitrary number of messages between components. It is not a feature to disable in exchange for both other letters. A design can be placed on a network where partitions are unlikely, but the algorithm still has behavior when one occurs. The impossibility result says an asynchronous system cannot guarantee both atomic consistency and that formal availability in every execution that permits those lost messages.

Put one replica on each side of a cut. A write reaches the left replica. A later read reaches the right. No message crosses the cut. To remain available, the right replica must eventually answer from its local information. That local state is indistinguishable from an execution in which no write occurred, so returning the old value is reasonable locally and violates linearizability globally. Waiting for evidence of the write preserves linearizability and violates availability. The missing message, not a weak implementation, creates the indistinguishable histories.

The durable process probe takes the waiting branch. n0 cannot reach a majority, so it does not acknowledge sequence 4. The n1 and n2 side can still make progress because it has a majority. That does not mean every client loses availability, and the probe does not implement the read path required to establish full linearizability. It means this schedule rejects operations presented to a minority rather than allowing both sides to commit independent log suffixes.

Real interfaces expose more than a binary label. A write can fail quickly, time out with an unknown outcome, be accepted into a local queue, or return stale data with a version. Different operations in one product can choose different contracts. A catalogue read and a payment authorization need not make the same decision. The theorem constrains the guarantees possible under the model; it does not choose which incomplete answer is useful to a particular caller.

The AP branch, and why an integer clock isn’t enough for it

My toy took the CP road, and I’m going to keep walking it, but the fork deserves one real experiment, because the AP road hides a trap I waved past when I set vector clocks aside near the top. The AP promise is “both sides of the partition keep answering, we reconcile the divergence later.” Reconcile how, exactly? You come out of a partition holding two versions of the counter that were written independently on the two sides, and you have to decide whether one is simply newer than the other (keep the newer, discard the older) or whether they’re genuinely concurrent conflicting writes (in which case you cannot pick one, you have to merge them, or you lose data). That is precisely the question a Lamport clock, a single integer, cannot answer, and this is where “throws away one piece of information” stops being a footnote and starts deleting someone’s money.

Here’s the failure, run both ways. Two clients start from the same state and write concurrently on the two sides of a partition, one sets the balance to 150, the other adds 50 interest, and neither client saw the other:

$ python3 vector_clock.py
  writeA: set balance=150   lamport=5  vector={'A': 3, 'B': 2}
  writeB: add 50 interest   lamport=5  vector={'A': 2, 'B': 3}

  LAMPORT: ts equal (5); tie-break by node name -> writeA 'wins'.
           last-writer-wins KEEPS ONE, silently DROPS the other. the 50 interest vanishes.
  VECTOR:  relation(writeA, writeB) = CONCURRENT (incomparable) -> conflict, must merge

Lamport hands both writes the timestamp 5, sees a tie, breaks it by node name, and declares writeA the winner. The 50 interest is gone. Silently. Nobody will ever know it existed, because a total order has no vocabulary for “these two didn’t happen in any order at all,” it can only rank, so it invents a ranking and throws the loser away. That’s the piece of information the parenthetical warned about, and on the AP branch it’s the whole ballgame.

The vector clock carries one counter per participant instead of a single integer. Version x precedes version y when every component in x is less than or equal to the corresponding component in y and at least one is smaller. Here writeA is {A:3, B:2} and writeB is {A:2, B:3}. writeA is ahead on A’s component and behind on B’s, so neither dominates the other. The honest verdict is concurrent. The store can retain both siblings and let code that understands the object decide whether and how to merge them.

The 2007 Dynamo paper describes this design for Amazon’s highly available key value store: vector clocks capture causality between object versions, concurrent branches can be returned to clients, and application logic can reconcile them. That claim is about the system in that paper, not every present service named Dynamo and not every eventually consistent store. The paper also describes truncating vector clocks when they grow, which introduces another compromise between metadata size and accurate ancestry.

My replicated log avoids sibling versions by routing changes through one elected leader and one ordered history. It pays for that order by refusing a minority write. The vector clock branch accepts that histories can fork and retains the information needed to notice the fork. Last writer wins would make the metadata smaller by selecting one branch, but for these two operations the tie breaker silently discards a live update. The clock cannot supply the application semantics needed to combine “set balance” and “add interest.” It can only refuse to pretend that one caused the other.

Exactly-once, revisited

The durable run makes one exactly-once claim that can be stated without hand waving: for client c, sequence 3, the committed counter history contains one increment and a retry returns the stored result 3. The operation, identity, and result share the replicated log. Killing and restarting the processes does not erase them.

Move one effect outside that log and the boundary breaks. Suppose the committed operation means “charge a card, then increment a paid order count.” The leader calls a payment service, the payment succeeds, and the leader dies before recording success. A retry sees no committed deduplication entry and charges again. Recording completion before calling the payment service reverses the failure: a crash can leave a completed marker for a charge that never happened.

The counter’s log cannot atomically commit state owned by an unrelated payment service. The downstream service must participate in the identity protocol, perhaps by accepting the same idempotency key and durably returning the original result on retry. Another design records an intent, drives a recoverable state machine until the external action is confirmed, and exposes intermediate uncertainty. A transaction can cover both mutations only when both resources participate in a transaction protocol with the required failure semantics. Deduplication inside one component does not cross an external side effect by assertion.

Even inside one log, the identity contract has edges:

same client, same sequence, same operation     return the stored result
same client, same sequence, different payload reject the protocol violation
new sequence, previous sequence still unknown preserve the client's ordering rule
sequence older than retained dedup state       cannot promise exactly one effect

The probe checks only the first row. Its entry comparison would notice a conflicting payload during replication, but the client path should reject reuse explicitly rather than silently return the earlier result. It does not support pipelined client operations or garbage collection.

A monotonically increasing sequence per durable client session can reduce storage to a high water mark plus the latest result when requests must arrive in order. Out of order pipelines require a window or a map of completed sequences. Snapshots can fold old identities into state, but a snapshot must preserve enough information to reject any retry the public contract still permits. Restarting a client with a forgotten session id creates a new identity domain and may repeat an old business action.

“Exactly once” is therefore incomplete without naming the effect, the atomic boundary, and the retention interval. This counter demonstrates one effect inside one replicated state machine for six retained client sequences. It does not establish exactly once delivery, exactly once external calls, or an unlimited retry lifetime.

One counter is easy. A billion counters need a map.

The three-machine log keeps one counter correct. But a real system has millions of keys, and they won’t all fit on one group of three machines, nor should they, you’d want to spread them across many groups for capacity and throughput. So shard: split the keyspace across many independent replicated groups, each group a little cluster like the one above, each owning a slice of the keys. Which raises the last question in the post, given a key, which group owns it?, and the obvious answer is a quietly catastrophic one.

The obvious answer is hash(key) % number_of_groups. It works until you add a group, and then almost every key changes owners, because changing the modulus reshuffles the whole mapping. I measured it, 100,000 keys, growing from 4 groups to 5:

$ python3 hashing.py
  100000 keys, grow 4 nodes -> 5.
  naive  hash % N:         80000 keys moved  (80.0%)
  consistent hash ring:    10455 keys moved  (10.5%)

Eighty percent of the keys moved. In a real system, “a key moved” means gigabytes of data physically copied between machines, so a naive hash % N turns “add one machine” into “restripe the entire dataset,” which is why you can’t grow the cluster during business hours. The fix is consistent hashing: instead of hash % N, hash both the keys and the machine ids onto the same circular number line, and assign each key to the first machine clockwise from it. Add a machine and it lands at one spot on the ring, stealing only the keys between it and its counterclockwise neighbor, the keys near that one arc, and every other key stays exactly where it was. Same growth, 4 groups to 5, and only 10.5% of keys moved instead of 80%. The essential property is that adding a machine disturbs only the keys near where it lands on the ring; every other key keeps its owner, so growth is local instead of global. That part is real and it’s the whole point.

But that clean 10.5% hid something ugly, which I only noticed when I stopped counting moves and counted how many keys each machine actually owns:

5 machines, ideal 20% each:   0.2%   9.9%   10.5%   20.0%   59.4%

One machine holds 59% of the data; another holds 0.2%. A single hash point per machine drops it at one random spot on the ring, and random spots leave wildly uneven gaps, so a “balanced” ring is nothing of the sort. It’s also why only 10.5% of keys moved instead of the ~20% you’d expect for one-in-five: the new machine happened to land in a small arc. The lucky-low move count and the ugly balance are the same fact, and I’d have shipped the pretty number and never known one node was carrying the whole cluster.

Before reaching for a fix I had to know whether I’d just been unlucky. One ring showing 59% could be a freak of the particular names n0 through n4; maybe I’d stumbled onto the single worst arrangement and the ring is usually fine and I was about to over-correct a fluke. So I re-ran it two hundred times, each with a fresh naming of the same five machines, and looked at how loaded the busiest one was:

$ python3 hashing_variance.py
  busiest share over 200 rings: min=26.1%  median=43.1%  mean=45.3%  p95=67.9%  max=82.3%
  fraction of rings where the busiest machine exceeds 2x fair share (>40%): 117/200 = 58%

Not a freak. The median ring has its busiest machine at 43%, more than double its fair 20%, and in 58% of rings somebody is carrying at least twice their share. My 59% was on the unlucky side of typical but nowhere near the worst, one ring in the two hundred put a single machine at 82%, and even the single best ring out of two hundred tries still had someone at 26%, a third over fair. The single-point ring isn’t occasionally lopsided, it’s reliably lopsided. So the pretty 10.5% move count wasn’t hiding a bad ring, it was hiding the normal behavior of this design, and if I’d shipped after one run I’d have shipped a design that cooks a random machine most of the time.

One repair is virtual nodes: hash each physical owner onto the ring many times under derived identifiers, so it owns many small arcs scattered around the circle instead of one large random arc. With 50 virtual points per owner, this five owner simulation flattened:

5 machines x 50 vnodes:   18.1%   19.9%   20.3%   20.6%   21.1%

Everyone owns close to a fair 20 percent in this sample. Adding an equal weight owner should move about its eventual share of keys, drawn in small pieces from many existing owners instead of one neighboring arc. The 2007 Dynamo design uses virtual nodes for incremental scaling, heterogeneous capacity, and movement across multiple peers. Other systems use different partition tables, rendezvous hashing, or explicitly balanced token assignments. The measurement supports this implementation and key distribution, not a universal requirement that every production hash ring use the same mechanism.

Fifty vnodes flattened five machines nicely, but that just moved the question: how many do you actually need, and how does the imbalance fall as you add them? So I swept the vnode count and measured, for each, the busiest machine’s load as a multiple of the average, which is the number that actually matters, because the busiest machine is the one that falls over first:

  vnodes=  1:  mean peak/mean = 2.341   worst carries +134% over fair
  vnodes=  2:  mean peak/mean = 1.965   worst carries  +97% over fair
  vnodes=  5:  mean peak/mean = 1.515   worst carries  +52% over fair
  vnodes= 10:  mean peak/mean = 1.373   worst carries  +37% over fair
  vnodes= 20:  mean peak/mean = 1.246   worst carries  +25% over fair
  vnodes= 50:  mean peak/mean = 1.170   worst carries  +17% over fair
  vnodes=100:  mean peak/mean = 1.114   worst carries  +11% over fair
  vnodes=200:  mean peak/mean = 1.088   worst carries   +9% over fair
  vnodes=500:  mean peak/mean = 1.053   worst carries   +5% over fair

The overload does not fall linearly. Moving from 1 virtual point to 50 reduced mean peak overload from 134 percent to 17 percent in these runs. Multiplying the points by another ten reduced it to 5 percent. I have not derived a general rate for the maximum load, and fitting 1/sqrt(v) to nine observations would not supply one. The result depends on the number of physical owners, number of sampled keys, hash function, token placement, and statistic being reported. The measured claim is the table: more independently scattered points reduced this experiment’s peak imbalance with diminishing observed returns.

The map is still not a storage system. If each key exists on one owner, that owner dying makes the key unavailable even though its assignment remains computable. A replicated design maps a key to a group, or walks the ring to several distinct eligible owners. “Distinct” must include failure domains: three processes on one host, three hosts on one rack power feed, or three zones behind one failed router do not tolerate the failures their count suggests.

Capacity is not uniform either. If one owner has twice the disk or request capacity, equal token counts deliberately waste it. Weighted token counts can assign more arcs to that owner, but bytes and work are different weights. Ten thousand tiny hot keys can overload a CPU while consuming less disk than one cold object. A useful placement model needs measured load, not only the count of hash positions.

Membership also changes the agreement problem. A process cannot independently notice a fifth owner and start sending it keys while peers still use a four owner map. Clients would compute different destinations for the same key. The membership configuration therefore needs a versioned source of truth, and moving a range needs a handoff protocol: copy existing state, capture concurrent writes, confirm the new replica has caught up, change routing, and only then retire the old copy. Raft’s joint consensus mechanism uses overlapping old and new configurations for changes to a voting group. A sharded data store may use a separate metadata consensus group and per-shard migrations. Consistent hashing limits which ranges move; it does not make the move atomic.

The hash itself must be stable. Python intentionally randomizes its built-in string hash between interpreter processes unless configured otherwise. A placement function using that value could remap the keyspace after a restart with no membership change at all. The probes use an explicit digest so the same bytes map to the same position across processes. That mundane choice is another piece of durable agreement: every participant must run the same hash algorithm, serialization, token width, and configuration version.

the machine that voted after forgetting

The child processes fail by stopping and later recovering from stable state. They do not fabricate a term, alter an entry, impersonate a peer, or send different truthful-looking histories to different recipients. That is a crash recovery model. Calling it crash stop would be inaccurate because n0 returns. The distinction matters because recovery adds a new way to violate an assumption: a process can forget state that should have survived.

The persisted vote is the smallest example. Suppose n2 votes for n0 in term 5, sends the response, and records voted_for only in memory. It crashes before the next disk write. After restart, term 5 remains on disk but the vote is empty. n1 asks, n2 votes again, and two candidates can each collect a majority:

n0 quorum: {n0, n2}
n1 quorum: {n1, n2}
overlap:   {n2}

The two majorities intersect exactly where the forgotten promise lives. Persisting the vote before replying prevents this crash recovery version of a double vote. It does not protect against a process that deliberately violates the rule.

I ran the latter case as a separate negative control. n2 answers yes to both candidates in the same term:

$ python3 byzantine_doublevote.py
N=3, term 5. two candidates run at once: n0 and n1. n2 is Byzantine (double-votes).
  n0 collected 2 votes (self + n2's lie).            majority=2 -> n0 thinks it WON: True
  n1 collected 2 votes (self + n2's SECOND vote).    majority=2 -> n1 thinks it WON: True
  => TWO leaders in term 5.

There is no higher term to resolve this pair. Both candidates claim term 5 and both present a majority. Ordinary majority intersection guarantees a shared member, but safety relied on that member obeying the one-vote rule. Authentication can prove that n2 signed both votes. It cannot make the two decisions compatible or undo a client response already produced. Evidence of equivocation helps remove or punish a faulty participant after detection; the protocol must prevent that participant from creating contradictory committed results in the first place.

For the fault model used by Practical Byzantine Fault Tolerance, n >= 3f + 1 replicas and quorums of 2f + 1 make the overlap large enough to contain an honest replica when at most f are faulty:

n = 4, f = 1, quorum = 3
minimum intersection = 3 + 3 - 4 = 2
at most one of those two can be faulty
at least one honest replica remains in the intersection

The arithmetic explains why a single liar cannot create two valid three-of-four certificates when honest replicas refuse incompatible protocol messages. It is not a proof of an arbitrary protocol. Message phases, authentication, view changes, request ordering, checkpointing, and the exact conditions under which an honest replica votes are part of the argument. Castro and Liskov’s Practical Byzantine Fault Tolerance describes one concrete system with this fault threshold.

The threshold also belongs to a model. Different trust assumptions, synchrony assumptions, trusted hardware, failure detectors, or quorum certificate rules can change the construction and sometimes the replica count. Writing 3f + 1 beside the three line double vote does not turn the counter probe into a Byzantine fault tolerant service. The measured result is smaller: a single equivocating voter defeats two-of-three majority election.

the schedules I did not run

One successful failure schedule is weak evidence for a protocol because concurrency creates many schedules. The parent delivered entry 2 before entry 1, duplicated a prefix, dropped one client response, isolated one leader, and killed two processes at selected boundaries. It did not enumerate every boundary between persistent writes and replies.

Consider sequence 5. n1 appends locally, n2 appends, n1 marks the entry committed, n2 learns the new commit index, and the client receives a response. A kill can occur before or after each step. Before majority replication, the operation may disappear and the retry must be allowed. After majority replication but before the client response, the operation may survive and the retry must deduplicate. After the response, every future successful leader must retain it. A test should place failure at each boundary, vary which replica survives, and verify the client contract rather than only final equality.

Log repair has a similar state space. The stale process can be missing a prefix, have an extra suffix from an old term, share an index but not a term, receive the same append twice, receive appends out of order, or restart during repair. The probe covers a missing predecessor, an identical duplicate, and one conflicting suffix. Raft’s safety properties quantify over all reachable combinations, which is why the paper includes an election restriction and a formal specification rather than relying on a transcript.

A model checker can explore a finite abstraction of those interleavings and search for an invariant violation. Useful invariants would include: no two different commands become applied at one log index; committed client identities have one stored result; an acknowledged operation remains in every later leader’s history; a process grants at most one vote per term; and a commit index never moves backward. Those are private implementation obligations, not reader exercises. I have not run such a model checker for this probe, so the article does not claim the protocol is correct outside its asserted schedules.

The storage path needs adversarial work too. SIGKILL preserves already completed writes on this machine. Power loss can interrupt the device after the operating system accepted an fsync, depending on the filesystem and hardware stack. A production log needs record boundaries, length fields, checksums, monotonic indices, and recovery rules for a torn or corrupt tail. A snapshot needs a checksum and an atomic relationship with the retained suffix. Disk full, permission failure, and an fsync error must stop the node from acknowledging durable state. The JSON probe raises an exception in many of those cases, but it does not inject or classify them.

The transport is still controlled. Pipes do not create delayed packets that arrive after a new term, half-open connections, duplicate RPC responses from a previous attempt, or backpressure from a slow follower. The term check should reject stale requests, but that path deserves an actual delayed-message control. Autonomous timers would also make liveness an observed property rather than a parent instruction. I have not run three socket processes with independent timers and random process death, so no sentence here attributes such a result to this experiment.

Reads remain the largest semantic omission. Replaying a committed prefix after restart shows what state a node can derive. It does not authorize any follower to answer a current read. A leader that was partitioned from a newer leader may still believe it is active until it observes a higher term. If it serves its local count immediately, it can return stale data after a completed write in the majority partition. A linearizable read path must establish that the responder is still entitled to answer, often through a fresh quorum exchange or a lease whose clock and delay assumptions are explicit. The negative history checker demonstrated the failure shape, but the service has no read implementation to test.

Configuration changes are another consensus decision. Adding n3 cannot be a local edit to an integer named N. If old members commit with an old majority while new members commit with a new majority and the two quorums do not intersect correctly, two histories can advance. Joint configurations or another staged mechanism preserve overlap while membership changes. The consistent hash migration has the same requirement at a different layer: all routers must know which version of placement state governs a key while its bytes move.

None of these omissions invalidates the six-count transcript. They limit what it supports. Directly measured: three child processes recovered persisted state after SIGKILL; the scheduled reorder was rejected; duplicate delivery did not append; one lost response deduplicated; one conflicting suffix was replaced; and all three processes recovered count 6. Derived: the timeout collision probability and quorum intersection arithmetic. Externally established: the Raft, linearizability, CAP, Dynamo, and PBFT mechanisms linked in the relevant sections. Predicted but not measured here: correctness with autonomous elections, socket faults, storage corruption, reconfiguration, long logs, and concurrent client histories.

the first counter, with the missing state visible

The opening program sent five increments to A and tried to send five to B. It had no operation identifier, so a retry could not be separated from new work. It had no agreed order, so noncommuting operations could diverge. It had no commit boundary, so one copy could not tell whether its state was provisional or promised. It had no durable term or vote, so a restarted participant could not remember which leader it had accepted. It had no log prefix check, so reordered delivery had no place to be rejected. Asking the network to deliver the same command twice was never enough to make two state machines behave as one.

The final recovered state contains the information the first two integers lacked:

term=3
log terms=[1, 1, 1, 2, 2, 3]
committed prefix=6 entries
client c completed sequences={1, 2, 3, 4, 5, 6}
counter=replay(committed prefix)=6

When the response for sequence 3 vanished, the committed identity made the retry return 3 without another increment. When isolated n0 invented a term 1 sequence 4, the commit boundary kept it from becoming a promise. When n1 and n2 committed another sequence 4 in term 2, the client identity preserved the requested effect. When n0 returned, the matching prefix exposed exactly where its history stopped agreeing, and only the uncommitted suffix was replaced. When n1 died after returning sequence 5, n2’s durable majority copy carried that response into term 3.

The two original values, 5 and 4, could not answer which one was right because the program had recorded only effects, not decisions. The replicated log does not make loss or crashes disappear. It records enough about each decision that a later process can distinguish a retry from a new request, a prefix from a hole, a promise from a proposal, and a current leader from an obsolete one. The remaining uncertainty is now visible at the boundary where the system must refuse to answer, rather than hidden inside two integers that both claim to be the count.