Election algorithms, agreement and consensus notes — Unit 3

Many distributed algorithms require a 'coordinator' or 'leader' node (e.g., a master node in a database cluster, or a centralized mutual exclusion coordinator).

⇒1.1 The Problem

If the leader node crashes, the system must agree on a new leader. The process of choosing a new leader in a decentralized way such that everyone agrees on the outcome is called an Election Algorithm.

Assumes every node has a unique ID, and every node knows the IDs and network addresses of all other nodes. The node with the highest ID always becomes the leader.

⇒2.1 The Process

When node `P` notices the leader is dead:

• 1. `P` sends an `ELECTION` message to all nodes with higher IDs.
• 2. If no one replies, `P` wins and sends a `COORDINATOR` message to everyone.
• 3. If a higher node replies with `OK`, `P` drops out. The higher node then starts its own election.

It's called the 'Bully' algorithm because the biggest node always forces the others into submission.

Does not require nodes to know everyone else's ID, just their logical successor in a ring.

⇒3.1 The Process

• 1. Node `P` notices the leader is dead. It creates an `ELECTION` message containing its own ID and sends it to its successor.
• 2. When a node receives an `ELECTION` message, it adds its own ID to the list in the message and passes it on.
• 3. When the message circulates back to the originator `P`, it sees its own ID in the list. `P` knows the message has made a full circle.
• 4. `P` looks at the list, picks the highest ID, and circulates a `COORDINATOR` message declaring the winner.

Elections are a specific form of a broader problem: Consensus. How do independent nodes agree on a single value (e.g., agreeing to commit a database transaction)?

⇒4.1 Properties of Consensus

A valid consensus algorithm guarantees:

• Agreement: All non-faulty nodes agree on the exact same value.
• Validity: The agreed value must have been proposed by at least one node.
• Termination: Every non-faulty node eventually decides on a value (the algorithm doesn't run forever).

Reaching consensus is easy if everything works. It is notoriously difficult when things break. We classify failures into two types:

• Crash Faults: A node simply stops working and goes silent. The network might drop a message. This is relatively easy to handle using timeouts.
• Byzantine Faults: A node continues to run, but acts maliciously or erratically. It might send false information, lie about its state, or send conflicting messages to different nodes. This is extremely difficult to handle.

In 1985, Fischer, Lynch, and Paterson published a mathematical proof that shocked computer science.

⇒6.1 The Theorem

In a fully asynchronous system (where there is no upper bound on network delay), it is mathematically impossible to guarantee consensus if even a single node might crash.

Because the network can be infinitely slow, a node can never tell the difference between a crashed node and a very slow node. It cannot safely proceed.

Workaround: Real-world systems use timeouts to bypass FLP, sacrificing pure mathematical certainty for practical reliability.

A classic thought experiment to illustrate Byzantine Faults.

⇒7.1 The Setup

Several generals are surrounding an enemy city. They must agree to either 'Attack' or 'Retreat'. If some attack and some retreat, they will be defeated. They communicate via messengers.

However, some generals are traitors. Traitors will lie. They will tell General A to attack, and tell General B to retreat, trying to cause confusion. How can the loyal generals reach agreement?

Lamport proved that to survive `f` Byzantine (traitor) nodes, the system must have at least `3f + 1` total nodes.

⇒8.1 Why 3f + 1?

If there is 1 traitor, you need 4 total nodes. If the traitor lies, you need a clear majority of loyal nodes to outvote the liar. With 3 loyal nodes and 1 liar, the loyal nodes can cross-verify messages and determine who is lying.

BFT algorithms are highly complex and network-heavy. Blockchain technologies (like Bitcoin) are fundamentally massive BFT consensus engines.

Used in distributed databases to ensure a transaction that spans multiple servers is committed cleanly (either all servers commit, or none do).

⇒9.1 Phase 1: Voting

The Coordinator asks all participants to prepare to commit. Participants write data to a temporary log and reply 'VOTE_COMMIT' or 'VOTE_ABORT'.

⇒9.2 Phase 2: Decision

If the Coordinator receives 'COMMIT' from everyone, it sends 'GLOBAL_COMMIT'. All participants finalize the write. If even one aborts, it sends 'GLOBAL_ABORT'.

Two-Phase Commit is a 'blocking' protocol. It handles participant crashes well, but fails catastrophically if the Coordinator crashes.

⇒10.1 The Blocking State

If the Coordinator crashes during Phase 2, after participants have voted 'COMMIT' but before they receive the final 'GLOBAL_COMMIT', the participants are stuck. They hold locks on their database rows indefinitely, waiting for a dead coordinator.

Three-Phase Commit (3PC) attempts to fix this with an extra 'Pre-Commit' phase, but is overly complex and rarely used in practice.

Invented by Leslie Lamport, Paxos is the gold standard for crash-fault-tolerant consensus. It guarantees safety (nodes will never agree on two different values) under any asynchronous network conditions.

⇒11.1 Roles in Paxos

• Proposers: Propose values to be agreed upon.
• Acceptors: Vote on the proposed values. A majority (quorum) is needed.
• Learners: Find out what value was chosen.

Paxos uses a two-phase protocol (Prepare and Accept) with strictly increasing proposal numbers to prevent conflicts.

⇒12.1 The Magic

If a Proposer wants to push value 'A', it sends a Prepare request with a high number `N`. Acceptors promise not to accept any future proposals with a number lower than `N`.

If the Proposer gets a majority promise, it sends an Accept request for 'A'.

Because it relies on majorities, Paxos can survive the crash of a minority of nodes and continue functioning perfectly.

Paxos is incredibly difficult to understand and implement. Raft was designed in 2013 specifically to be 'understandable' while providing the exact same safety guarantees as Paxos.

⇒13.1 Strong Leadership

Raft achieves consensus by first electing a strong Leader. All log entries flow in one direction: from the Leader to the Followers. If the leader fails, Raft triggers a rapid, randomized election to choose a new one.

Raft is the consensus engine behind modern tools like etcd (which powers Kubernetes).

• Elections: Bully (highest ID wins) and Ring algorithms select a coordinator.
• Consensus: Achieving agreement despite failures. FLP proved it impossible in purely asynchronous networks.
• Faults: Crash faults are easy; Byzantine faults (malicious actors) require complex `3f + 1` node setups.
• Algorithms: 2PC handles distributed commits but blocks on coordinator failure. Paxos and Raft are the industry standards for non-blocking, fault-tolerant consensus.