Understanding Master Election with Paxos: Lease Algorithm Explained

Previous article: Paxos Theory Introduction (2): Multi‑Paxos and Leader Readers who haven’t read the earlier piece are advised to review it first.

Master

A Master is a role defined such that, within a selected set of nodes, at any moment there is at most one node acting as Master, or none at all. This strict single‑point definition is widely used.

In distributed storage, a Master is elected so that all reads and writes go through it, guaranteeing the latest value. Arbitration modules also often rely on a Master.

Master Election and Its Relation to Paxos

Electing a Master requires a strong‑consistency algorithm; we use Paxos for this purpose. However, the election algorithm itself is generic and can be paired with any strong‑consistency protocol without being tied to Paxos internals. Our goal is a Paxos‑decoupled implementation where Master election only uses Paxos APIs.

Paxos Engineering Application

The engineering side involves API design and state machines, which are omitted here. The following diagram (from the paper "Paxos Made Live") illustrates the concept:

In short, Paxos determines a sequence of operations; by implementing callbacks (state‑machine transition functions) for these operations, nodes execute the same ordered callbacks, ensuring consistent state across nodes.

Master Election Lease Algorithm

The BeMaster operation proposes that a node become Master. Any node can issue this operation unless it already knows another node is Master. After learning another node is Master, a node must wait a timeout before attempting BeMaster again. If a node learns it is Master, the timeout window after the BeMaster request defines its Master term .

How to Combine the Lease Algorithm with Paxos?

BeMaster can be treated as a Submit operation whose value carries the node’s information.

The callback performs two actions: (1) if the value’s node is not itself, wait for the timeout before retrying BeMaster; (2) if the value’s node is itself, promote to Master and let the term expire at T(BeMaster) + timeout .

How Is Algorithm Correctness Ensured?

Consistency is guaranteed by Paxos: the chosen value is the same across nodes, preventing election conflicts.

The lease algorithm ensures single‑point Masterness: because the constant T(BeMaster) < T(Know other as master) , a Master’s expiration occurs before any other node believes the Master has expired, preventing concurrent Master claims.

Question: In the diagram, why does the Master term start from the BeMaster request rather than from a successful BeMaster response? Readers familiar with Paxos should answer easily.

Master Renewal

During a Master’s term, successfully completing another BeMaster operation extends the term, leading to a highly stable Master under normal conditions.

Each term is assigned a version. The following example illustrates why:

Node A repeatedly renews its Master status, but Node C loses communication with A. After learning of A’s second renewal, Node C receives no further updates and assumes A’s term has expired, prompting it to issue BeMaster, which violates the algorithm’s guarantee.

The root cause is that Node C lacks the latest Master information. Introducing a version (similar to an optimistic lock) solves this: BeMaster includes the previous version; if the version is stale, the request fails, preventing incorrect Master takeover.