🐫 Addendum: Consensus & More

Paxos is used as a learning substrate Paxos is hard to understand and harder to implement right. This project keeps the scope to single-decree Paxos — narrow enough to be tractable (~2 weeks) and deterministic enough to verify cleanly. in this series. This addendum hosts my observations and intuitions on some core concepts revolving around this space that may help fast-track other learners. It also aims to funnel readers to actual canonical work that others have done.

Foundations #

Why Consensus Matters #

A decision made by a single machine is lost if that machine fails. Consider a system with multiple machines that collaborate across a network to make decisions and progress towards a goal. The machines may fail but the decisions that the system makes must survive that loss. That’s the key idea behind Distributed Consensus¹.

Quorums Are About Intersecting-Sets #

For a cluster of nodes to make decisions, they would have to agree on the same truth. The set It’s “set” because the membership is what matters and not just the count. of participating nodes needed to decide on common truths is a quorum.

Any two sets that must not disagree with each other have to share a member, so if we don’t know which pairs (of sets) must not disagree, then it’s easier to make every pair overlap. That’s why a majority quorum rule is a convenient way to guarantee safety — that two quorums share at least one node so that the system does not forget a decision. Single-decree Paxos follows this instinct.

Imagine that a leaderless cluster of 5 nodes makes a decision and then one of the nodes has to discover what that decision was. Let’s hand-wave how this happens, just that "decided" For the example below, the entire caravan (with multiple caravan formations) makes a decision when enough parchments carry that information. No caravan formation can see “enough” parchments — it may only see what its own parchment says and dispatch couriers to get information from others. What is true of the system and what a participant observes may have a gap, that’s why we need to get intersecting sets. is a property of a set of durable records For the example below, the parchment that the caravan formations use is the durable record. Parchment is private and durable. For the example, writing the campsite on the parchment doesn’t mean that the caravan formation believes the group has agreed. Instead, it just means that this caravan formation will never write a different campsite. . Every node only knows its own state and none of the others. Though, it may send messages to the others to obtain that information.

To narrate Figure 2 , one of the caravan formations (e.g. A) has suggested to “camp @ the northern oasis”. Couriers from A ride out to all the others. We’ll call the set of formations that received the message and successfully wrote it to their own parchment, \(Q_{W}\).

1. in Case A and Case B, a sandstorm happens and separates them into two groups \(\{A, B\}\) and \(\{C, D, E\}\). So the couriers don’t reach C, D and E to pass the message. Only A and B have written Yes, A will write on its own parchment paper. Implementation-wise, it’s easier to write code with common code-paths so we “self-loop” and allow A to send a message to itself. "northern oasis" to their parchments. So \(Q_{W} = \{A, B\}\).

2. in Case C, the sandstorm partitions the group differently. In addition to A and B, node C also manages to write the info to its parchment. The couriers don’t reach D and E. \(Q_{W} = \{A, B, C\}\)

Later, one of the formations wishes to know where the group is headed, so it asks everyone. \(Q_{A}\) is the set of nodes that respond.

The figure below is drawn from the Chronicler’s point-of-view (us readers / the simulator), no caravan formation (node) sees the entirety of the drawn panels in the diagram.

When reading the original Paxos paper ², the narrative uses a quorum of parliamentarians and the ballots they cast. So, I was primed with the thinking that “quorum = enough votes to act”. The parliamentary setting actually has the counting-framing codified within a book ³. On further understanding, the protocol actually depends on more general point: a quorum is enough witnesses that no conflicting decision could have happened without at least one of them knowing about it.

I consider Takeaway 1 to be essential for learning Consensus Algorithms because it suggests that there are knobs within these formalised algorithms. Turning them can yield specialised variants of these algorithms for specific, practical use-cases. For example, the knob of relaxing the majority rule constraint is a stepping stone towards FlexPaxos. We could deviate from our leaderless implementation in v0 and consider leader-based approaches as another knob for us to turn.

The Knob Table: Paxos Variants as Points in a Design-Space #

My framing is that the named algorithms are the same core with different knobs turned. My v0’s Single-decree Paxos is the outcome of setting all the knobs conservatively, to prioritise safety:

• no leader
• single decision — single decree
• it’s 2-phased and both phases run every time
• always follows majority-quorum rule

Each of the Paxos-variants below relaxes one of those settings and absorbs the cost in some other way. The trade-offs are easier to see if we read the settings as axes within a design space instead of a list. Happily, this also lets us ask the important question: which of these settings does my workload / use-case really need?

Six Knobs #

These are roughly in the order that the series encounters them.

1. The quorum rule

   Which pairs of sets must overlap, and how large each must be. This is the main point I made in the previous section about quorums. Majority-everywhere is the setting that declines to distinguish the pairs.

2. Scope: single-decree or log of decisions?

   Is the system deciding one thing (single-decree), or a sequence of things? Paxos decides one value, immutably, forever. Almost every real system wants an ordered log of decisions, which means running multiple instances of the core protocol.

3. Leadership

   Is any node a distinguished proposer, or may anyone propose? A leader is not required for safety — v0 has none. It exists to improve latency and to reduce contention. It may also simplify implementations.

4. Phase elision

   Must the first phase run before every decision, or can it run once and amortised across multiple decisions? This knob only becomes available once knobs 2 and 3 are turned.

5. The message path.

   Does a proposal travel through client \(\Rightarrow\) coordinator \(\Rightarrow\) acceptors, or can the client reach the acceptors directly? Removing the hop removes a message delay and creates the possibility of collisions.

6. Ordering discipline.

   Must every decision be totally ordered against every other, or only against those that actually conflict?

The Table of Knobs #

That’s why I’m framing it as a “design space” rather than a catalogue of algorithms. None of them are without trade-offs / assumptions that may not hold depending on the conditions of where the algorithm is deployed.

Essence of the Algos #

Here are some points that I’ve picked up from implementing / reading on how variants are implemented.

Some correctness pointers to consider based on some initial misconceptions I had:

1. Multi-Paxos elides Phase 1 (leader election) per leader term across all slots, instead of for every decision.

   I think my misconception stemmed from the fact that leader election is discussed first in the paper, so it’s easy to conflate that it’s per-decision.

2. Fast Paxos’ fast-quorum is bigger than a majority-rule to make recovery feasible so that progress is ensured. See the 3-way set intersections within the Fast-paxos paper ⁸

3. Flex-Paxos’ quorum is asymmetric when comparing phase 1 vs phase 2, not across two of the same phases.

Signposts #

Towards Generalised Consensus #

The “Generalized Consensus” series¹⁶ builds its framework from the ground up: a small set of hierarchical, goal-oriented rules first, with the familiar named algorithms arriving later as things that happen to satisfy them.

A Trailer to “Generalized Consensus” #

The series¹⁶ opens by re-framing distributed consensus as a matter of distributed durability rather than being about agreement between agents in a cluster. It says that agreement is actually the mechanism to solve the problem of distributed durability and that prior art has mainly focused on mechanisms — the way that particular algorithms operate — rather than what the system should deliver (requirements focused on the problems). Through that frame, quorum intersection becomes a property to make a saved decision findable again. It shows Durability and Discoverability as two sides of one coin. A rule that makes data durable without keeping it discoverable can still stall the system — which is just as bad as losing the data because the availability requirement fails either way.

If durability is the requirement, then instead of being a law to follow, durability rules are parameters to inject. Just like the earlier metaphor of knobs in a design-space, we are free to relax conservative rules (e.g. Majority-quorum) and may conjure up durability policies that fit the shape of modern use-cases on modern infrastructure. In a classic Dependency Injection move, the focus then shifts to durability policies that are pluggable… so long as a few custodial restrictions These make the system predictable: a rule may only depend on the current set of participating nodes, node properties (e.g. availability zone) must be static, and no external variables may be depended on. are met. A fundamental observation follows: different leaders may hold different rules at the same time. This heterogeneity is what turns the job from a configuration option into a systems problem — a ruleset is now a decision in its own right and it’s replicated state that whoever takes over next has to discover and reconcile before it can act.

We learn that there’s a paper (“A Generalised Solution to Distributed Consensus”¹⁵) that is similarly-named but the two actually aim to do different things The two works do overlap when discussing the concepts of revocation and flexible durability rules. . The paper works on demonstrating a single algorithm that is general enough for the named protocols to show themselves as its instances while the blog-series establishes a general framework for adapting a consensus system to the environment that it has to run in.

The magic of this series is in how it layers fresh constraints/concepts in a way that they naturally reduce to an earlier point that it would have established. The rules in the early parts are what the later ones obey — the 11-parts should be read in order for them to have a satisfactory, snap-together feel.

A Conceptual Keystone: Why Revocation Is a Primitive #

Reading “Generalized Consensus” ¹⁶ with an implementation already written is a different experience from reading it cold. v0 is a deterministic, single-decree Paxos simulator. It’s small enough that the OCaml type system is the primary subject and Paxos the learning substrate — and small enough that revocation never came up. “Generalized Consensus” makes revocation a rule and shows how other concepts reduce to it. The implementation it suggests fuses revocation back into the steps around it, and that fusion of mechanisms is where I would have gotten it wrong.

Revocation Is Not Only a Lock-Out #

Rule 2a in “Generalized Consensus”¹⁶ opens by asking one thing of an agent The series’ generic term for whoever is currently entitled to make a decision on the cluster’s behalf. In a leader-based system there are at least two kinds: the leader, which fulfils requests, and the coordinator, which changes leadership. before it may take any action: revoke every previous agent’s ability to make further progress. Read quickly, this revocation rule sounds like clearing the desk before starting work — housekeeping.

Read past the prohibition and the same rule is an act of discovery: stated as what an agent must stop, it also fixes what the agent finds. This second reading is the one I arrived at late.

The foundations above and “Generalized Consensus” start from the same premise: a quorum is a set of nodes, and majority is convenient rather than necessary. That’s Takeaway 1 and their shared upstream is FlexPaxos The writer of the “Generalized Consensus” series¹⁶, Sugu Sougoumarane, published his own account of the same relaxation in 2016⁷, cited in the knob-table.  ⁶, cited in both. Mine stops there. I treated intersection as a safety property: something that stops the asker It’s a term I used for an example above about quorums being set intersections. from contradicting a decision that already happened (Case A is the counter-example). That reading turned Takeaway 1 into a question about which design-knob yields which protocol-variant: a question about algorithms, asked from inside them. The series declines that reading rather than reinterpreting it — ‘intersecting quorums’ appears in its list of terms it will not use, replaced by discovery, revocation and candidacy.

Three observations on the framework’s rules:

1. The sweep that stops the incumbent is what produces the discovery of state, and what it finds determines which requests get honoured after a failure. To stop the incumbent, the revoking set must contain a node from every combination the incumbent could have made a request durable with. A set that hits every such combination has also seen every request that reached one — and some of the merely-attempted ones.

2. Which nodes belong in the revoking set is a separate question from who is taking over (i.e. the candidate). Paxos and Raft ask for a majority, and a majority Specifically, prepare message for Paxos, RequestForVote for Raft. satisfies revocation and candidacy at once, so the two never appear as separate requirements. Relax the quorum rule and they need not be the same nodes.

3. How far the revoking set has to reach isn’t set by the incumbent either. A coordinator An agent that sits outside the cohort. It health-checks the nodes and, when it concludes there’s a failure, appoints a new leader. Several coordinators can be deployed — placed across availability zones — and they aren’t aware of each other. They may overlap in their purview too. must revoke every leadership the ruleset The durability policy made concrete: the list of cohort nodes, which of them are eligible to lead, and for each of those, the node combinations that count as durable. Every cohort node stores it. permits — not just the one it thinks is currently leading. Each of those primaries has to be left unable to complete a request, either by recruit-ing Asking a node to move up to your term number. It accepts only if yours is higher. You don’t have to say why — what the nodes get used for is decided afterwards. it directly or by denying it every combination of nodes it could complete with. Under majority-everywhere a single majority discharges that for all of them at once; once leaders A leader is a node in the cohort currently empowered to accept requests and make them durable. It serves until its leadership is revoked; there’s no expiry. The series also calls these primaries when listing which nodes are eligible. hold different rules, each has to be accounted for separately. That is what makes a heterogeneous ruleset safe: a write need only reach any leader’s quorum, and recovery finds the alternates.

None of the three is dimensioned by what the new agent intends to do. Something that self-contained looks like it should be folded into the mechanisms it serves — into discovery, into candidacy, into the ruleset change itself.

In this framework, it nearly is. A coordinator achieves all four Part 11 verbatim: “A single step achieves the above four goals: The coordinator increments its current term number and sends a message to recruit all the nodes in the cohort.” in one step: it increments its term and sends a single recruitment message to the cohort The full set of nodes responsible for meeting the system’s durability requirements — the ones that persist logs. Coordinators are not part of it. , and revocation, candidacy and discovery arrive as goals of that one step rather than three steps of their own. Recruitment doesn’t even distinguish revocation from candidacy — the same message that revokes is the message that recruits a candidate. The node a coordinator intends to install as the next leader. It becomes the leader when the coordinator delegates its term to it.

And yet the three sit differently in the rules. Candidacy never appears as a rule at all. Revocation of candidacy and revocation of leadership are the same act, and that is not a coincidence: revocation works by disrupting durability, and the only durability rules in the system apply to leaderships. Discovery has a rule of its own, but the mechanism that satisfies it is what the series calls a 'serendipitous side effect' The writer’s words, not mine. of revocation. Revocation alone is a rule with nothing that it can further reduce to.

The Entry Price for Manufactured Authority #

What breaks is our intuition on the costs of revocation.

Suppose we fuse the concepts: revocation becomes a step inside a procedure — e.g. something a leadership change does — so its cost must belong to that operation.

It doesn’t, though. Authority is a quantity distributed across the cohort’s persisted term “Generalized Consensus” adopts Raft’s terminology. term is Raft’s name for the number that orders decisions; Paxos calls it a proposal number. Every node persists the term it last agreed to, rejects requests from any lower term, and can be recruited into a higher one. numbers, not a property that an agent holds. A term number means nothing until nodes have been recruited into it. Acquiring authority and draining it from the incumbent are one act seen from two ends Authority accumulating on the coordinator’s side, the ability to reach a quorum draining on the incumbent’s side , rather than being two steps in sequence. Revocation can’t be folded into discovery or candidacy because it’s not a precondition of those steps; they are things that revocation does.

Revocation is achieved by recruiting nodes into a higher term, and there are two routes:

1. recruit the incumbent directly, so that it relinquishes leadership and it waits for further requests

2. recruit the nodes that the incumbent relies on for durability, so that those nodes stop accepting its requests — like a mutiny

Both routes are recruitment; neither is a separate revoking instruction.

If revocation is part of what a leadership change is, then a leadership change must be disruptive — the incumbent stops being able to complete requests, and writes stall until a successor is established. There’s no version of it that skips the revoking.

The framework shows otherwise. A planned leadership change is handed to the current leader as a request it fulfils like any other, with the quorum for that sole request widened to include the intended leader’s rules. Once applied Irreversible commitment of a decision — e.g. a commit for a database, an fsync for a filesystem. Only safe once the decision can no longer be abandoned. , the leader steps down and the successor observes the event and promotes itself, and no new term is started Part 8 verbatim on planned leadership change: “Again, there is no need to start a new term number for this method.” . This leader-method is possible because the leader already holds what a coordinator would have had to manufacture, so there’s no second writer to lock-out. This is not some special case of cleverness. There’s no need for a new term, so there’s nothing to recruit which means nothing to revoke. It’s the same operation, just that the router varies The agent that actually brings in the change. Here, instead of being the coordinator, it’s the leader itself. .

A Coordinator Is Not a Supervisor #

A process that watches a set of nodes, health-checks them, decides if one of them has failed, and installs a replacement is a strikingly familiar shape. In some systems, such an entity does hold authority of its own as a supervisor. That’s the mental model that I initially had for the coordinator, carried over from OTP¹⁸ supervision trees. A coordinator connects to every node in the cohort, keeps its picture of the current leader, term and ruleset up to date, and walks a decision-tree that ends with one of two actions: change the leader, or do nothing.

A supervisor’s authority is structural — it never acquires it at the moment it acts; it already has it because of how the system was built. It spawns its children, holds links to them, and the parent-child relationships exist before any failure does. A supervision tree makes parenthood exclusive by construction, so a supervisor never has to consider whether some second supervisor is restarting the same child at the same moment.

A coordinator, as described in the framework, has none of that. It doesn’t create the leader, it doesn’t own the log. Any authority it has, it has to go and acquire — and the only instrument for that is a term number.

A supervisor is a lock with a process-tree around it. The series considers such a lock and sets it aside because a lock can’t carry a proof. We can’t bound how long a process takes, so a timeout can elapse mid-action; and clocks drift, so an agent can believe it still holds time everyone else considers expired. Either way, a second agent starts acting, and sequentiality is violated. Part 5 gives both reasons in its detour on distributed locks.

So, even though exclusivity is available, it’s not provable, and the term number machinery is what gets built instead. The “Generalized Consensus” series is careful, rather than dismissive, about this distinction. It keeps locks and timeouts viable as long as the trade-offs are understood, and notes that Vitess runs this way Part 5: “We shouldn’t dismiss this approach… In fact, Vitess employs this approach.” .

An agent that cannot prove it is alone has to assume that it is being raced. And because a crashed coordinator is indistinguishable Per the FLP result ¹², which the series cites for exactly this. from a slow one, it has to assume it will never find out. That is why the scope for revocation is every leadership the ruleset permits, not just the incumbent’s.

An arch is the picture I keep coming back to. Its keystone is not a separate kind of stone — it’s cut and set in the same course as the stones beside it, doing the same job they do.

Looking Forward #

Earlier, I said that the fusion is where I would have gotten it wrong. v0’s scope also let the quorum-checks use the convenient, number-based approach — majority-everywhere makes a count sufficient — even though Takeaway 1 had just argued that a quorum is a set and size is merely a property of it.

271
272
273
274
275
276
277
278
279
280
281

  (** Quorum predicate for both phase 1 and phase 2 of paxos.*)
  let is_quorum_reached cluster_size rs =
    match Proposer |> get_role rs with
    | WaitingForPromises wfp ->
        wfp |> is_quorum_reached_on_promise_wait cluster_size
    | ProposerAccepting pa ->
        pa |> is_quorum_reached_on_proposer_accepting_wait cluster_size
    | _ ->
        failwith
          "is_quorum_reached called on non-proposer state (must be \
           WaitingForPromises or ProposerAccepting)"

A quorum typed as a count can’t express node-identity rules — which combinations of nodes qualify — and combinations are exactly what a revoking set has to hit. The count isn’t confined to one signature either; it’s threaded through the helpers beneath it. Changing that will be v1’s problem. Knowing that now, before v1 exists, is most of what reading the series bought me.

There’s still something that I can’t yet judge:

I expect to find out when I write v1. Preferably not as a hobby.