Beyond Multi-Paxos

Everything up to here is one algorithm: a majority of acceptors, one elected leader, a fixed membership, and disks that either work or stop. Each of those four is a choice, and each one has a paper that takes it apart. This chapter is the field guide to those papers as paros implements them.

Two rules govern the whole act. Plain Multi-Paxos is permanent and first-class: a cluster with a fixed membership, no matchmakers and a majority quorum system exchanges exactly the messages of the previous chapters. Every mechanism below is opt-in configuration data, and the presence of its code turns nothing on. The simulation draws that data per seed, so one campaign runs the plain deployment and the extended one. The safety oracles hold in both.

Play it. Act IV is ten levels, one for each mechanism below.

• act4/flexible-quorums — choose the reach of each phase over four acceptors, and try to dodge the overlap.
• act4/the-grid — decide two slots on two columns, then send a stray Accept outside a slot's column and watch the tally ignore it.
• act4/quorum-reads — serve a read at a follower from a row's vote watermarks, and hold one read that is not covered yet.
• act4/the-handoff — hand the leadership on under the same ballot, then try to hand it on a second time.
• act4/matchmaking — register a campaign, read the histories back, and close Phase 1 over every configuration in them.
• act4/reconfigure — grow the acceptor set onto a spare, and get a command chosen under the new configuration.
• act4/garbage-collection — raise the watermark, then retire a removed acceptor with the evidence in hand.
• act4/matchmaker-generations — replace the matchmaker set through stop, reconstruct, bootstrap, decide and publish.
• act4/faulty-records — damage one accepted record, then put each Promise that arrives into its CTRL case.
• act4/the-wiped-node — erase a disk, take the library's refusal, and keep the survivors deciding.

Flexible quorums

Act I derived safety from one fact: any two majorities share an acceptor. Read the derivation again and something smaller is enough. Phase 1 must learn about every value that Phase 2 may have chosen. Nothing needs two Phase-1 quorums to share an acceptor, and nothing needs two Phase-2 quorums to share one either. Only the two phases must meet, which as arithmetic is q1 + q2 > n.

That releases the steady state. With four acceptors, q1 = 3 and q2 = 2, a write needs two answers instead of three. The next election pays for that with three promises. The picture below is what no single run shows: two Phase-2 quorums that miss each other completely, beside a Phase-1 quorum that must meet both.

 flowchart TD
    P2A["Phase-2 quorum, q2 = 2:<br/>A0 and A1 choose SET x=1"]
    P2B["Another Phase-2 quorum:<br/>A2 and A3 — it shares<br/>no acceptor with the first"]
    P1["Every Phase-1 quorum, q1 = 3:<br/>here A1, A2 and A3"]
    A0((A0))
    A1((A1)):::shared
    A2((A2))
    A3((A3))
    P2A --- A0
    P2A --- A1
    P2B --- A2
    P2B --- A3
    P1 --- A1
    P1 --- A2
    P1 --- A3
    classDef shared fill:#c97a2b,stroke:#7a4718,color:#fff

Three plus two is five and there are four acceptors, so no Phase-1 quorum can miss both voters. paros asks every quorum question through one boundary, so this is deployment data and not a rewrite. QuorumSystem::Flexible { q1, q2 } is one variant, QuorumSystem::cross_intersects is the well-formedness rule, and no tally changed when it landed.

In the code. QuorumSystem::Flexible, QuorumSystem::cross_intersects, AcceptorConfig::has_phase1_quorum, AcceptorConfig::has_phase2_quorum (crates/lib/paros-core/src/membership/); the example paros-core/examples/flexible_quorums.rs. Paper: Howard, Malkhi and Spiegelman, Flexible Paxos (docs/references/papers/flexible-paxos/). Play it: act4/flexible-quorums.

The acceptor grid

A quorum does not have to be a count. Lay six acceptors out in two rows of three, call any whole row a Phase-1 quorum, and call any whole column a Phase-2 quorum. A row and a column of one grid always cross in exactly one cell. The two phases therefore meet by geometry, and the safety argument does not change.

The grid buys throughput. Each slot goes to one column, so each acceptor sees a third of the writes and the acceptor tier scales with the number of columns. It costs availability of a new shape. Failure now depends on which acceptor is down and not on how many, because one dead acceptor leaves its column short.

The column is slot % cols. That is a pure function of the slot, not a field on the wire. A restarted leader and a handoff successor derive the same column. A decision is judged by that column alone. An acceptor outside it may vote for a stray copy, honestly and safely, and its vote still counts for nothing.

In the code. QuorumSystem::Grid { rows, cols }, QuorumSystem::column_of, QuorumSystem::row_of, AcceptorConfig::has_phase2_quorum_in (membership/); ColocatedNode::propose_in (node.rs); the example paros-core/examples/acceptor_grid.rs. Paper: Whittaker et al., Scaling Replicated State Machines with Compartmentalization §3.2 (docs/references/papers/scaling-rsm-compartmentalization/). Play it: act4/the-grid.

Quorum reads

The grid takes the writes off the leader. The reads must not go back to it. The quorum read does not involve the leader at all, and on a grid it asks less.

Ask a Phase-1 quorum one thing each: what is the highest slot you have voted in? The quorum is a row of the grid, or the membership under a majority. Take the largest answer, and serve the read at any replica once that replica has applied the slot. A write acknowledged before this read began was chosen by a Phase-2 quorum. The Phase-1 quorum you asked crosses that quorum, so the largest answer sits at or above the write.

Two properties are worth naming. There is no clock anywhere in this path, which is exactly what the paper's read leases give up. And an acceptor raises its watermark when it votes, not when a slot is chosen. A read can therefore land on a watermark that a half-finished slot raised, and it waits for that slot to arrive. The wait costs the reader time, and it never costs the client a stale answer.

The argument is single-configuration, so a read is bound to the configuration it opened against. A PreReadAck carries the answerer's configuration ballot, and a node abandons its open reads when it learns a newer configuration.

Every public Read uses this path. A client may ask any node or any replica, and the server never redirects it: the leader, a follower, a spare and a replica all serve the read the same way. A Read at the tail waits for new records for the time that its wait_ms gives. A Read below first_seq gets the answer truncated, and the client starts again at the floor that the answer names. The simulation's client draws the server at random, and the client-history check judges every read.

In the code. QuorumRead, QuorumReads (quorum_read.rs); ColocatedNode::quorum_read(ctx) and quorum_read_in(ctx, row) (node/quorum_reads.rs); the Read RPC (paros.proto), which the driver parks until the read is confirmed and serves from the fold (crates/lib/paros-roles/src/node/log_reads.rs); Acceptor::vote_watermark (acceptor.rs); Message::PreRead, Message::PreReadAck (message.rs); Replica::covers, Ready::read_states. Paper: Whittaker et al., Compartmentalized Paxos §3.4, Paxos Quorum Reads. Play it: act4/quorum-reads.

Proxy leaders

A leader does two jobs per command. It sequences: it picks the slot, which is serial and cheap. And it broadcasts: it sends the Accept to the column, collects the Accepteds, and sends the Commit to every learner. That second job costs 3f + 4 messages through one process, and it is why adding acceptors or replicas makes a classic leader slower. Only the first job has to be the leader's.

So the leader hands the very same Accept to a proxy leader instead. The message names the proxy as its reply party and still names the leader as the hint an acceptor adopts. The proxy fans it out to the column, folds the Accepteds, and emits the Commit. The leader sends one message and receives one, whatever the width of the grid. A proxy contributes nothing to the decision. It votes on nothing, orders nothing, and adopts no ballot, so a chosen value is still what a Phase-2 quorum durably accepted at one ballot, and moving the broadcast to another process cannot break agreement.

The proxy is not a second Phase-2 engine. It is the proposer's own round tally on another process, plus routing. Which proxy a slot goes to is slot % proxy_count, a pure function the driver may override, and a count of zero is the plain deployment, message for message. A leader delegates only on a settled leadership: an election's recovery and its gap fills always run on the leader, so a fresh leadership depends on no proxy. A handoff successor re-delegates what it inherited with itself as the hint.

Liveness under a dead proxy is the leader's. It keeps a delegated round for every slot it hands out, re-delegates on every beat, and after a budget of unanswered re-delegations it takes the round back and runs it itself. The fallback is always the classic Phase 2, and safety never rests on it, because two fan-outs of one (slot, ballot, command) are idempotent at every acceptor.

The proxy's side of the same bargain is bounded retention. It re-fans-out its open rounds on every beat, and a round the acceptors answer closes on their Accepted or their Nack. One class of round is never answered: a slot every acceptor has already compacted past, whose Accept is ignored without a reply because refusing a chosen slot would depose a leader for nothing. A delegation delayed on the wire until after the leader took the round back and the cluster truncated the slot would be re-fanned-out for the rest of the process's life. So after a budget of unanswered re-fan-outs the proxy evicts the round. An eviction is not a decision: nothing is emitted, the slot is not remembered as done, and a leader that still needs the round re-delegates it on its next beat and, failing that, takes it back. The budget is the driver's, born buggified.

The proxy runs on a process of its own, driven by the third driver beside the node's and the matchmaker's. It has nothing to persist: no promise, no log, no format marker, so a crash reboots it empty and the leader's next re-delegation rebuilds every round it still needs. One proxy process serves many journals. It keeps one proxy leader per journal, and the journal identifier on each message selects it, so no round of one journal meets a round of another. In the simulation the proxies are their own process group, drawn per seed like the matchmakers, killed and revived by their own attrition regime, and judged by one claim the node's own Commit already answers to: every Commit a proxy emits must be backed by a Phase-2 quorum of durable accepts at one ballot, as the audit folded them from the acceptors' own reports, never from the proxy's tally.

The model checker that proves this found one rule the core was missing. A delegated round left no record at the leader, so a handoff successor that crashed rebooted with its allocator rewound, and a duplicated Relinquish re-installed the authority at the old frontier. Two commands then ran at one (slot, ballot). A grid leader proposing outside its own column had the same hole. The rule that closes both is in the next section.

In the code. ProxyLeader, ProxyReady, ProxyLeader::expire_stale (proxy_leader.rs); Custody, Rounds::open_delegated, Rounds::take_back, Rounds::stalled (proposer/rounds.rs); Delegation, ColocatedNode::propose_in, ColocatedNode::take_back_delegated (node.rs, node/phase2.rs); Party, Audience::Proxy (message.rs); Config::proxy_count (contract/config.rs); ProxyConfig, ProxyJournal; the model checker models/proxy.rs; the example paros-core/examples/proxy_leader.rs; the driver paros::run_proxy (crates/lib/paros-roles/src/proxy_leader.rs), the harness's ProxyProcess and PROXY_GROUP (paros-sim/src/process/, roles.rs), the audit's observe_proxy_decision (paros-sim/src/audit/state.rs). Paper: Whittaker et al., Compartmentalized Paxos §3.1. No level yet.

The replica tier

Every node in the previous sections has two jobs. As an acceptor it votes on the log. As a replica it learns the chosen log, walks it in slot order and serves it to the clients that read it. The two jobs scale in opposite directions. An extra acceptor makes each quorum bigger, so the protocol gets slower. An extra replica only learns, so the clients get more read capacity. When both jobs share one process, you cannot scale one without the other.

So paros can split them. A replica node learns and serves reads, and it never votes. It receives the Commits that the leader or a proxy leader sends to every learner, and it persists each chosen value in the same record format a node uses. That record is not a vote: a replica is in no configuration, it answers no Prepare and no Accept, and it acks no beat. When a Commit is lost, the replica sees the gap in the next beat's watermark and asks the leader for the missing range. When the range was truncated, the acceptor that answers sends a TrimmedTo instead, and the replica jumps to the trim point, as any node below the floor does. The one replica that answers the client for slot s is s % replica_count, so each replica sends a share of the replies. Today the node that the client asked still sends the reply; the reply owner is the data a future client library will use. One replica process serves many journals. It keeps one replica node and one store per journal, and each read names the journal it reads.

Splitting the tiers raises a question about the other side: must an acceptor that no longer serves clients still keep the chosen log? The code answers it one coupling at a time, and the answer is yes. An acceptor only truncates chosen slots. A new leader skips the slots that are already chosen. Garbage collection counts the chosen indices of a Phase-2 quorum. A lagging node or replica is healed from the acceptors' chosen values. So every acceptor keeps its chosen index and the chosen values. Since paros runs no application at all, there is nothing else an acceptor could shed: every acceptor is the same learner, whether or not replicas run beside it.

 flowchart LR
    L[leader]
    subgraph acceptors [acceptors: vote, keep the chosen log]
        A0[acceptor 0]
        A1[acceptor 1]
        A2[acceptor 2]
    end
    subgraph replicas [replicas: learn, serve reads, never vote]
        R0[replica 0]
        R1[replica 1]
    end
    L -- Accept --> A1
    L -- Accept --> A2
    A1 -- Accepted --> L
    A2 -- Accepted --> L
    L -- Commit --> R0
    L -- Commit --> R1
    R1 -- CatchUpRequest --> L

A replica runs on a process of its own, driven by the fourth driver beside the node's, the matchmaker's and the proxy's. Unlike a proxy it is durable: it keeps its chosen log on the same storage a node uses, with the same boot scan, the same format marker and the same crash seams, and a crash reboots it from its disk. The leader's beats and Commits reach it because the deployment map adds the replicas to every message addressed to the learners. In the simulation the replicas are their own process group, drawn per seed like the proxies and killed by their own attrition regime. Their disks sit outside the storage budget, because a replica's record is never a copy a quorum needs. The same checks that judge every node's walk judge them, as does the claim that every learner has converged at the end of the run. A killed replica that comes back below the floor the acceptors kept raising is healed by a trim-point jump, and the sweep proves that path is taken. Clients read the journal from replicas too, and the simulation requires that a replica served one.

A replica is also where the paper's leaderless read happens. A client asks a replica for a quorum read; the replica asks a row of acceptors how far each has voted, takes the highest answer, and replies from its own state once it has applied that far. It is the same tally a node runs, so the same argument makes it linearizable, and no clock is involved. The simulation sends some quorum reads to replicas, judges them by the same client history as every other read, and requires that a replica served one.

The client's write is still acknowledged by the node it asked, because a client talks to one endpoint and waits for one answer. Each slot's reply owner is computed all the same, and the simulation requires that the owner of an acknowledged slot applied it, which is the fact a future client library that talks to replicas would rely on.

The garbage collection rule does not change. The paper's Scenario 3 lets a configuration be forgotten once replicas outside it hold the chosen prefix. paros still counts only acceptors, because they are the ones whose records the next Phase 1 reads.

In the code. ReplicaNode, ReplicaReady, ReplicaCounters (replica_node.rs, whose module doc holds the coupling analysis); Config::replica_count, Config::reply_owner (contract/config.rs); ReplicaId (membership/ids.rs); WriteOp::Learned (write.rs); the example paros-core/examples/replica_tier.rs; the driver paros::run_replica (crates/lib/paros-roles/src/replica.rs), the harness's ReplicaProcess and REPLICA_GROUP (paros-sim/src/process/, roles.rs); the replica's quorum read ReplicaNode::quorum_read_in and its journal read ReplicaNode::read_log; the jump below the floor ReplicaNode::trim_to. Paper: Whittaker et al., Compartmentalized Paxos §2.3, §3.3 and §3.4. No level yet.

Cooperative leader handoff

Leadership changes hands for two reasons, and only one of them needs an election. An election destroys the old authority and makes a successor rediscover the log through Phase 1. That is right when the old leader is gone. It is waste when the old leader is alive and wants to move. A rolling restart does that, and so does an operator who moves the leadership closer to its clients.

So the sitting leader hands its Phase-2 authority over instead. It sends the ballot, the allocator frontier, and the tail below that frontier. The tail is split into the slots it knows are chosen and the slots whose Phase 2 is still open. The two parts tile the range exactly, which is what lets the successor skip Phase 1: it may re-propose what it was told about, and the range holds nothing else. Gap filling stays off, because a Noop needs a promise quorum's report to license it and this successor collected none.

Three rules carry the safety. Abdication is synchronous with the decision: relinquish_to queues the message and becomes a follower in the same call, so emitting the message without abdicating is not expressible. The successor is named inside the payload, so a duplicate or a misroute cannot hand one authority to a second node.

The third rule is one hop only: can_relinquish requires LeadershipOrigin::Elected. A replayed message could otherwise reinstall an authority at a node that has already handed it on, beside the successor that still uses it. A second hop costs an ordinary election, and the general case would cost a new durable fence.

The fourth rule is that the allocator frontier is durable by construction. A successor refuses a replayed Relinquish that would rewind its allocator, and the allocator is rederived from the successor's own accepted log at every boot. So a leader records every round it opens in its own log whenever its promise allows, whether the round is delegated to a proxy, and whether or not the leader sits in the slot's column. A record outside the column is the stray copy the grid already admits, a vote that counts for nothing. Without that record, a successor that crashed after exercising an installed authority rebooted blind, and the proxy model checker re-installed a duplicated Relinquish on it.

In the code. ColocatedNode::relinquish_to, ColocatedNode::can_relinquish (node/handoff.rs); Message::Relinquish, LeadershipOrigin (message.rs); RecoveryPolicy::Inherited (proposer/recovery.rs); the record every open round leaves, record_own_round (node/phase2.rs). Paper: Nawab, Agrawal and El Abbadi, DPaxos, SIGMOD 2018, the Relinquishment section; design note docs/analysis/consensus/dpaxos-leader-handoff.md. Play it: act4/the-handoff.

Matchmakers and reconfiguration

Every chapter before this one reads the membership once, at boot, and never changes it. A real cluster replaces machines. The obvious method puts the new membership through the log as a command, and it has a known hazard: the new configuration must be in force for the very election that installs it.

Matchmaker Paxos moves that decision to a separate, tiny service. A candidate first registers its ballot and the configuration it intends to use with a matchmaker set. It sends no Prepare until a matchmaker quorum has answered. The replies carry the registrations they hold, and the union of those above the maximum watermark is the campaign's history H_b. A reply leaves out a belief when a later registration repeats its configuration, so the union stays the same. A registry that failed campaigns fill with one configuration then fits in one reply. Phase 1 then fans out to H_b ∪ C_b, and it completes only with a promise quorum of every configuration in H_b. It is never a quorum of the union, and the core's tests pin that negative case.

The ledger distinguishes a belief from a fact. An ordinary campaign registers the configuration it believes is in force, and a reconfiguration campaign registers an operator's explicit change. The effective configuration is the highest-ballot reconfiguration registration that a matchmaker quorum holds. An ordinary campaign whose histories name a different one abandons, adopts it and campaigns again. So a node that missed a completed reconfiguration cannot be elected under the superseded one. Beliefs never trigger that abort, because two candidates that adopt each other's beliefs flip-flop forever.

A reconfiguration is a round change. A configuration is bound to a ballot and is never edited, so the leader moves to a fresh ballot registered with C_new. It stalls new commands for one matchmaking round trip plus one Phase 1, and it resigns afterwards if the change removed it. A joining node promises the new ballot before Phase 2 reaches it, and it heals as a replica. A removed node keeps answering Phase 1 for the ballots it took part in, because removed is not shut down.

On a cluster with no matchmakers a reconfiguration request is refused, and it is never quietly honored.

One matchmaker set serves every journal of a tenant. The set keeps one registry per journal, in one store, and every matchmaking message names its journal. So each journal has its own watermark, its own history and its own effective configuration. A storage fault in the store closes the whole set. A handover moves the registries of all its journals to the next generation together. One message cannot carry the registries of every journal, so the handover is paged: a stop answer and a bootstrap each carry a page of journals, and a member counts only when it has every page.

In the code. Matchmaking, Registration, RegistrationKind, MatchStep::StaleConfiguration (matchmaking.rs, matchmaker/state.rs, node/matchmaking.rs); Matchmaker (matchmaker.rs); ColocatedNode::reconfigure (node/reconfigure.rs); Ready::match_requests, ColocatedNode::on_match_reply. Paper: Whittaker et al., Matchmaker Paxos: A Reconfigurable Consensus Protocol (docs/references/papers/matchmaker-paxos/). Play it: act4/matchmaking and act4/reconfigure.

The GC watermark and retirement

Registrations accumulate, so a matchmaker must be allowed to forget. The rule for forgetting is the one place where a plausible answer is wrong. "The new configuration is installed, so the old one is deletable" is the rule DPaxos uses. Matchmaker Paxos's Appendix D shows why it does not hold.

A configuration may be forgotten under one condition. No future leader may need its Phase-1 quorum to learn a value that its Phase-2 quorum may have chosen. paros has no replica tier, and what it does have is stronger for this purpose. A node records a slot it learns chosen as its authoritative accepted record, before its chosen index advances. A truncated member refuses a Prepare below its floor.

So the condition has two parts. The leadership is settled, with no recovery, probe or repair open. And a Phase-2 quorum of C_b reports a chosen index at or past the election fence. The leader then asks the matchmakers to raise the watermark to its own ballot. Each matchmaker raises it durably before it acks, and refuses campaigns below it. The floor is effective only once a matchmaker quorum has acked, and only then does the leader name the retirable acceptors, members(H_b) \ C_b.

Retirement itself is an operator act, and the request carries the evidence. The operator reads the effective watermark from a leader's Inspect, beside the retirable list, and sends it in the retire request. The node honors the request under five conditions. It has matchmakers. It is not a member of the configuration it believes in force, and it is not the leader. The watermark sits strictly above the highest ballot that any configuration naming it was bound to. And the configuration it believes in force is bound to exactly that watermark.

The first three conditions are beliefs, and the third is volatile across a reboot. Without the fourth condition, "the cluster is done with me" would be the operator's assumption rather than a protocol fact. The fifth makes the belief fresh. A node learns its membership only from the messages it receives, so a member that never heard the configuration naming it, or that rebooted to the one it was deployed with, would pass the other four. Its belief must be the configuration the floor was computed over, neither older nor newer, before "I am not a member" means anything. Otherwise it refuses as stale, until a beat from the leader reaches it.

In the code. GcStep::Effective (collector.rs, node/gc.rs); ColocatedNode::may_retire (node/gc.rs); GcRequest, GcAck, Inspect.retirable, RetireRequest.gc_watermark. Design note: docs/analysis/consensus/matchmaker-gc-and-generations.md. Play it: act4/garbage-collection.

Matchmaker-set generations

The matchmakers are now the thing that cannot be replaced, so the matchmaker set is itself a chosen value. A set carries a generation, and every matchmaking message is fenced by it. A matchmaker answers its own active generation. It refuses every other generation with what it knows, and it never serves one.

The handover has five steps:

1. Stop. A quorum of M_g freezes durably. A frozen matchmaker registers nothing for g again, and it stays alive to vote and to point late proposers at its successor.
2. Reconstruct. Take the maximum watermark and the union above it.
3. Bootstrap. Every proposed member holds the successor durably, as pending.
4. Decide. Run single-decree Paxos over M_g.
5. Publish. M_g records the chain link, and M_{g+1} activates its pending bootstrap.

Step 4 is the reuse the architecture was built for. It is not a second Paxos kernel. It runs the same Proposer and Acceptor roles over a one-slot log, which is why the crate holds exactly one Phase-2 tally. Matchmaker quorums are majorities only, and the safety argument for the handover is made under that model alone.

Two liveness rules keep a frozen generation from wedging the cluster. Any node that meets a Stopped reply with no successor finishes the handover itself. And the driver abandons a phase that makes no progress, after a budget of election timeouts.

A sans-IO model checker proves the handover, in place of an argument. Concurrent reconfigurers run over the real types. Every message is dropped, duplicated or reordered, every matchmaker crashes at each durability seam, and every node reboots to its bootstrap belief.

The checker asserts three things after each step. At most one set is authoritative per generation. A chosen set is what a majority durably voted at one ballot. And every activated registry carries the complete reconstruction.

It bites. Publishing the bootstrapped proposal without the decree is red on its first seed. The checker also found that a rebooted node's reconfigurer reused the decree rounds of its earlier incarnation. That is why a Stopped reply carries the matchmaker's decree promise, and why the decree opens strictly above the maximum over the stop quorum.

In the code. MatchmakerSet { generation, members }, MatchmakerSet::has_quorum (membership/matchmaker_set.rs); MatchmakerReconfigurer (matchmaker/reconfigurer.rs); the decree (decree.rs, generic since #277); the checker (models/handover.rs). Design notes: docs/analysis/consensus/matchmaker-gc-and-generations.md and docs/analysis/consensus/matchmaker-interaction-verification.md. Play it: act4/matchmaker-generations.

Faulty records

Disks lose data one block at a time. A node comes back and one accepted record no longer reads: the value is gone, and the slot and the ballot survive beside it. That node now has three honest answers about the slot, not two. It voted and holds the value. It did not vote. Or it voted and no longer knows for what.

The third answer must stay its own answer. A node that reports it as "I did not vote" lets a candidate hear silence from a whole quorum. The candidate concludes that nothing was chosen there, and it decides something else. If the lost value was already chosen, that slot then holds two values. So a damaged record is reported as damaged, and a candidate that receives one cannot settle the slot from that report alone.

More answers settle it, which is the protocol-aware recovery of the CTRL paper. The leader keeps asking the acceptors that have not replied, and each reply puts the slot in one of three cases:

• Some acceptor reports a value at a ballot at or above the damaged record. The leader re-proposes that value, and the damaged acceptor writes it back as it votes.
• A whole Phase-1 quorum reports nothing that could hide a chosen value. The leader decides a Noop.
• Neither case holds yet. The leader waits.

In the code. Acceptor::faulty (acceptor.rs); Storage::faulty_entries (storage.rs); Proposer::fold_probe_promise, Proposer::resolve_probe (proposer/probe.rs). Paper: Alagappan et al., Protocol-Aware Recovery for Consensus-Based Distributed Storage (docs/references/papers/protocol-aware-recovery/); restatement docs/analysis/storage/ctrl-multipaxos-restatement.md. Play it: act4/faulty-records.

Background scrubbing

A boot scan finds a damaged record only when the node starts. A disk can rot a record that no client reads for months. If a second copy of that slot rots too, the value is lost while every node runs. So each tenant runs a scrubber. It reads every record of every journal of the tenant again, one pass after the other.

The scrubber is one process per tenant, the elected tenant coordinator. It does not do a quorum read. It asks each acceptor for its own copy of a page of slots. Each acceptor reads the page from its disk and checks each checksum. It returns the ballot and a hash of each record, never the bytes. The scrubber then compares the copies:

• A record that fails its checksum is damaged. The acceptor still holds the value in memory, so it writes the record again from that copy before it answers. This is the CTRL repair of the section above: the slot goes to the protocol, and no other path rewrites it. If the node restarts first, its boot scan reports the slot faulty, and the other acceptors repair it.
• Two copies of one slot under one ballot with different hashes are a mismatch. Paxos accepts one value per slot per ballot, so a mismatch is a bug, never rot. The simulation fails a run that finds one.

The scrubber writes its progress as an entry in the tenant's control journal. A newly elected scrubber reads that entry and continues the pass from there. A rate limit and a full-pass bound pace the reads, each with a floor.

In the code. LogStorage::scrub (crates/lib/paros-storage/src/lib.rs) reads and checks one page; ColocatedNode::repair_record (node.rs) and Acceptor::rewrite (acceptor.rs) write a damaged record again; machine/scrub.rs is the scrubber; ScrubProgress (tenant/scrub.rs) is its progress entry. In the simulation, a cold-rot scenario (paros-sim's world/scenarios/cold_rot.rs) damages a record on one disk while its machine runs, and a gate requires that the scrubber repairs a record no client read.

The wiped node

A crash costs a node everything it held in memory and nothing it wrote down. That is why paros keeps leadership in memory and promises on disk. Losing the disk is a different failure with a different answer.

A promise is the one thing a node may not take back. Having promised a ballot, it told a proposer that every lower ballot was finished there. That proposer may have chosen a value on the strength of the promise. A node that boots with an empty disk has no memory of it. The node answers a lower ballot and votes for what that ballot proposes. A quorum behind the older ballot then chooses a second value for a slot that already holds one.

Catching up does not help either. Commit replay restores chosen values, and a trim-point jump restores where the log starts; neither restores a promise, and the peer that answers does not know what this node has sworn. So a node that lost its disk does not rejoin, and the library enforces that rather than the harness or the operator.

Every store carries a durable format marker. The driver takes the operator's claim as data. It formats the store on a first boot, before the core reads a byte. It refuses an existing member whose store carries no marker. It also refuses a first boot on a formatted store, because that is two identities on one disk.

The marker is a store property and not protocol state, so the plain deployment persists the same two scalars it always did. What heals the cluster is a change of the acceptor set, which draws its successors from the live nodes.

The marker also records the configuration the store was formatted under: the bootstrap membership, the quorum system, the counts and the identity. The core reads them once, at construction, and counts every quorum by them, so they are safety inputs. An existing member whose operator now hands it a different configuration is refused too. A node that quietly switched from a majority to a flexible split, or to a membership missing a peer, would count quorums its peers do not. The operator restores the configuration the store was provisioned with, and changes the membership the only way it ever changes: by reconfiguration. The matchmaker's registry records its own configuration (its identity and bootstrap set) the same way. In the simulation an operator sometimes restarts a node or a matchmaker under an edited file, and the library has to refuse it before the restored file brings it back as the member it was.

In production the claim is not a flag on the start. A machine mints its own identity, a random node_id, the first time it starts on an empty data directory, and then waits, configured with no peer. parosctl init forms the cell with cell init, a single-decree Paxos on the cell's plan over the founding members it lists, every one an acceptor. Accepting the plan is forming: each member formats the stores of the cell's journals once, records that it did in a provisioning record beside them, then commits its vote, the plan, in its machine record; every later start is an existing member. A start therefore never formats: lost stores under a kept identity are refused as amnesia. A wiped volume takes its identity with it and comes back as a new machine with a new node_id, which never rejoins as the old one. A formation interrupted between its formats and its commit resumes by reading the disk, the rule the simulation's operator follows too.

In the code. LogStorage::formatted_config, LogStorage::format (crates/lib/paros-storage/src/lib.rs); BootKind::FirstBoot, BootKind::ExistingMember, BootRefusal::Amnesia, BootRefusal::ConfigMismatch (crates/lib/paros-tunables/src/lib.rs); Audit::boot_refused; provision_store (crates/lib/paros-storage/src/provision.rs), paros::machine::run_machine and MachineRecord (crates/lib/paros-machine/src/) and the machine's MachineRecord (crates/lib/paros-model/src/machine/record.rs). Play it: act4/the-wiped-node.

Many journals on one process

A journal service runs many logs on the same machines. The tempting design shares one Paxos instance and partitions its log by key. paros goes the other way: it shares processes, disks and connections, and never protocol state. Each journal is its own namespace, with its own ColocatedNode, its own ballots, its own log and its own store. Every proof in this book then holds per journal unchanged, and exactly one new property has to be shown: non-interference.

The journal id travels on the Deliver envelope, one per message, and the driver routes each message to its journal's node before the core sees a byte. Folding the id into the command fingerprint would not be enough. That protects the value an Accepted names, but a Prepare, a Promise, a Commit or a heartbeat carries no command at all, and it would cross journals silently. One Deliver per peer carries every journal. Inside the peer mailbox each journal has its own keep-newest lane, and the drain takes them round-robin, so a busy journal can only evict its own messages.

A storage fault quarantines its journal, not the process. The damage is scoped to one store. The journal's node is dropped and sends nothing, while the process keeps serving its other journals. After a short delay the driver re-opens the journal from its store, as if that one journal had restarted. A process whose every journal is quarantined at once has nothing left and crashes, which with one journal is exactly the old fail-stop rule. The copy budget is therefore per journal.

The simulation gives every journal its own audit and its own storage world, so every oracle in the campaign is keyed by journal without knowing it. A shared board carries what no single journal can see:

• every slot of a journal applies only a command appended to that journal;
• a quarantined journal sends nothing;
• a journal keeps committing while a sibling is held on every node for the chaos window;
• a node keeps serving its other journals while one is quarantined.

In the code. run_journals, JournalStores (crates/lib/paros-roles/src/node/, journals.rs); PeerMailbox (crates/lib/paros-roles/src/node/transport.rs); paros::observe::scenario::HOLD_JOURNAL, Audit::journal_held, Audit::journal_quarantined; crates/sim/paros-sim/src/audit/journals.rs; paros_sim::shape::journals.