Distributed Consensus - Paxos

 

Distributed Consensus — Class Notes

1. What Is Distributed Consensus?

Distributed consensus is the problem of getting multiple computers/nodes to agree on a value or state, even though:

• Nodes operate concurrently.

• Nodes communicate asynchronously.

• Nodes can fail unpredictably.

• The nodes are maintaining some mutable state.

This is essentially the same distributed-system environment we've been studying: concurrent + asynchronous + failure-prone processes.

The lecture focuses on Paxos as the consensus protocol.

---

2. Why Do We Need Consensus?

Imagine three replicas holding some mutable value:

Node A → Red
Node B → Red
Node C → Blue

The system needs to determine:

What value should everyone agree on?

We can't simply assume that one node is always correct because:

• A node might be down.

• A message might be delayed.

• A message might never arrive.

• Different nodes might have different information.

Therefore, we need a formal protocol for reaching agreement.

---

3. Four Requirements of Consensus

A consensus algorithm has four important properties.

① Termination

The process must eventually reach a decision.

In simple terms:

Don't wait forever.

Eventually, the system should decide on a value.

Proposal
   ↓
Consensus process
   ↓
Decision

If the algorithm never decides, it isn't useful.

---

4. Validity

The chosen value must be a value that was actually proposed.

Suppose:

Node A → proposes Red
Node B → proposes Blue
Node C → proposes Green

The consensus algorithm cannot suddenly decide:

Yellow

because nobody proposed Yellow.

So:

The decided value must come from a proposal.

The transcript describes this as integrity/validity: a process cannot simply invent the decided value.

---

5. Integrity

The lecture separates the formal requirements into:

Termination
Validity
Integrity
Agreement

Integrity means that if a process decides on a value, that value must have been proposed by some process.

So:

Proposed:
A → Red
B → Blue
C → Green

Allowed:
Red / Blue / Green

Not allowed:
Yellow

---

6. Agreement

Eventually, the processes must agree on the same value.

For example:

Node A → Red
Node B → Red
Node C → Red

Not:

Node A → Red
Node B → Blue
Node C → Green

The objective is:

All participating processes eventually reach the same decision.

---

7. Four Properties — Easy Memory

Remember:

Property	Simple Meaning
Termination	Eventually decide
Validity	Decide a proposed value
Integrity	Don't invent a value
Agreement	Everyone agrees

🧠 Memory trick

TVIA

Terminate → Valid value → Integrity → Agreement

---

8. What Is Paxos?

Paxos is a deterministic, fault-tolerant distributed consensus protocol.

Its purpose is to help nodes agree despite node failures and unreliable communication.

The lecture uses Paxos particularly in the context of replicated durable mutable state, such as databases.

The key idea is:

Multiple nodes
      ↓
Different information / failures
      ↓
Paxos protocol
      ↓
Consistent decision

---

9. Paxos and Replicated Databases

Imagine we have three replicas:

       Client
      /   |   \
     ↓    ↓    ↓
   Node A Node B Node C

Suppose we're storing some mutable value.

The replicas need to agree on the value.

Paxos helps establish a consistent result despite failures.

The lecture specifically connects this idea with Cassandra's lightweight transactions, where the nodes involved in the operation use Paxos-style consensus.

---

10. Important: Paxos Doesn't Always Make Progress

This is a very important distinction.

Paxos can guarantee a consistent result, but there can be situations where it cannot make progress.

In other words:

It is better to report failure than to return an incorrect answer.

For example, if there isn't enough information/participation to establish consensus, the system should say:

CONSENSUS FAILED

rather than:

Here is a value...

when that value isn't reliable.

---

11. Quorum — The Key Concept in This Example

The lecture then introduces a simple read example.

Suppose we have:

Client
   |
   +---------+---------+
   ↓         ↓         ↓
Replica A  Replica B  Replica C

The client reads from all three replicas.

Suppose all three return:

A → Restrepo
B → Restrepo
C → Restrepo

Then the system sees:

Restrepo
Restrepo
Restrepo

Clearly there is agreement.

So the client can return:

Restrepo

---

12. What If One Replica Disagrees?

Suppose we get:

A → Restrepo
B → Restrepo
C → Skinny

We have:

Restrepo = 2
Skinny   = 1

There is still a quorum for Restrepo.

Therefore:

Result → Restrepo

The important concept is:

A majority/quorum agrees on Restrepo.

---

13. What If There Is No Quorum?

Now suppose:

A → Restrepo
B → Skinny
C → Skinny

Actually, here Skinny still has a majority of 2, so Skinny would be the quorum result.

The failure case described in the lecture is when there is no quorum.

For example, with three replicas:

A → Restrepo
B → Skinny
C → another value

There is no majority.

Therefore:

No quorum
    ↓
No consensus
    ↓
Read fails

The system does not simply guess.

The lecture's key point is:

If there is no quorum, return a failure rather than return a potentially incorrect answer.

---

14. Why Quorum Matters

With three replicas:

        3 replicas
       /    |    \
      A     B     C

A majority is:

2 out of 3

So:

2 → Restrepo
1 → Skinny

means:

Consensus → Restrepo

But:

1 → Restrepo
1 → Skinny
1 → Something else

means:

No majority
     ↓
No consensus
     ↓
Failure

---

15. Happy Path vs Failure Path

Happy path

Client
  ↓
A → Restrepo
B → Restrepo
C → Restrepo
  ↓
Consensus
  ↓
Restrepo

Slightly imperfect but still successful

Client
  ↓
A → Restrepo
B → Restrepo
C → Skinny
  ↓
2/3 = quorum
  ↓
Restrepo

Failure

Client
  ↓
A → Restrepo
B → Skinny
C → Other
  ↓
No quorum
  ↓
FAIL

---

⭐ Big Picture: Where Paxos Fits

Connect this with the previous topics you've studied:

Distributed System
        ↓
No global clock
        ↓
        ├── NTP
        │    └── Approximate physical time
        │
        └── Vector Clock
             └── Event ordering / causality

Then:
        
Multiple nodes need to AGREE
        ↓
Distributed Consensus
        ↓
Paxos
        ↓
Agreement despite failures

🧠 One-line memory trick

Vector Clock tells us "what happened before what"; Paxos helps nodes decide "what should we all agree on."

And for the Paxos section, remember the four requirements:

Termination + Validity + Integrity + Agreement

and the practical rule:

If the system cannot establish a reliable quorum/consensus, fail rather than return a wrong answer.

---

paxos write:

Paxos — Class Notes

1. What is Paxos?

Paxos is a distributed consensus protocol used to help multiple distributed nodes agree on a value, even when nodes can fail or messages can be delayed.

A typical example:

Several database replicas need to agree that the value of a key should be "Flat White".

Paxos ensures that once a value is chosen, conflicting values cannot both become the agreed-upon value.

---

2. Paxos Happy Path

Even when everything works correctly, Paxos involves several communication steps between nodes.

Assume we have:

• 1 Proposer

• Several Acceptors

• A replicated key/value

• Value = Flat White

The basic process has four phases:

1. Prepare

2. Promise

3. Accept Request

4. Acceptance

---

Phase 1 — Prepare

The client asks a node to write:

Key: Coffee
Value: Flat White

The node handling the request becomes the Proposer.

The Proposer generates a sequence number / proposal number.

Example:

Proposal Number = 1
Value = Flat White

The proposal is sent to the other replicas, which act as Acceptors.

Important property of proposal numbers

The proposal number must be:

• Unique across the cluster

• Sortable / comparable

For example, it could contain:

Timestamp + Node ID + Random component

The important point is that proposals must be unambiguously ordered.

The proposal number is a distributed ordering mechanism, not a distributed counter.

---

Phase 2 — Promise

The replicas receiving the proposal become Acceptors.

Suppose the proposal is:

Proposal = 1
Value = Flat White

Each Acceptor checks the proposal number against the highest proposal number it has already seen for that key.

Rule

An Acceptor promises:

"I will not accept a future proposal with a number lower than this proposal number."

So if the Acceptor receives proposal 2000, it promises:

I will not accept proposals < 2000

Important:

Promise does NOT mean:

"I promise to accept proposal 2000."

It means:

"I promise not to accept anything lower than 2000."

---

What does the Acceptor send back?

The Acceptor returns information about:

• The proposal number it is promising

• Any previously accepted proposal/value, if applicable

On the happy path, suppose all nodes have nothing better to report.

They return:

Proposal = 1
Value = Flat White

The Proposer receives a quorum of responses.

---

What is a Quorum?

A quorum is enough nodes to establish agreement/progress.

For example, with 5 replicas:

5 nodes
↓
Need majority
↓
3 nodes = quorum

Paxos does not necessarily need unanimous agreement.

It needs a sufficient quorum.

This is critical because some nodes may be unavailable.

---

Phase 3 — Accept Request

After receiving a quorum of promises, the Proposer sends an Accept Request.

Example:

Proposal Number = 1
Value = Flat White

The Acceptors check again:

"Has anyone presented a higher proposal since I made my promise?"

If no higher proposal has appeared, they accept:

1 → Flat White

---

Phase 4 — Acceptance

The Acceptors confirm the proposal.

Once the Proposer has the required quorum of acceptances:

Proposal 1
Value = Flat White

is considered successfully chosen.

The Proposer can then tell the client:

WRITE SUCCESS

---

Paxos Happy Path — Easy Diagram

Client
  |
  | Write: Flat White
  v
Proposer
  |
  | Prepare(1)
  +---------------------> Acceptor 1
  |                       Promise(1)
  |
  +---------------------> Acceptor 2
  |                       Promise(1)
  |
  +---------------------> Acceptor 3
                          Promise(1)

       <---- Quorum of Promises ----

Proposer
  |
  | Accept(1, Flat White)
  +---------------------> Acceptor 1
  |                       Accepted
  |
  +---------------------> Acceptor 2
  |                       Accepted
  |
  +---------------------> Acceptor 3
                          Accepted

       <---- Quorum of Acceptances ----

Proposer
  |
  v
Client
WRITE SUCCESS

---

3. Important Paxos Scenario — A Better Proposal Appears

Now consider a more interesting situation.

The Proposer starts with:

Proposal 5
Value = Cafe Cubano

It sends:

Prepare(5)

But one Acceptor has already seen a higher proposal:

Proposal 8
Value = French Press

Therefore, that Acceptor cannot simply promise proposal 5.

It responds with the information about the higher proposal:

Highest proposal = 8
Value = French Press

---

What does the Proposer do?

The Proposer realizes:

"There is already a higher proposal that I need to respect."

Therefore, instead of continuing with:

5 → Cafe Cubano

it changes its proposal to:

8 → French Press

The other Acceptors may initially have been happy with:

5 → Cafe Cubano

but they had promised not to accept proposals below 5.

Proposal 8 is greater than 5.

Therefore:

8 > 5

So accepting proposal 8 is allowed.

The result becomes:

8 → French Press

---

4. Key Paxos Rule

The most important idea to remember:

Higher proposal numbers override lower proposal numbers.

Example:

Proposal 5 → Cafe Cubano
Proposal 8 → French Press

Because:

8 > 5

the higher proposal wins.

This mechanism allows Paxos to deal with competing proposals.

---

5. What Happens During Failures?

The happy path is relatively straightforward.

The difficult part of Paxos comes from scenarios such as:

• Proposer failure

• Acceptor failure

• Network delays

• Message loss

• Multiple competing proposers

• Two proposers making proposals simultaneously

• A higher proposal appearing halfway through the protocol

These situations can produce complicated protocol/message diagrams.

However, Paxos is designed so that these scenarios still preserve consistency and agreement.

---

6. Paxos Roles

Remember these three terms:

Proposer

The node that proposes a value.

Client
  ↓
Proposer

Acceptor

Nodes that participate in deciding whether a proposal can be accepted.

Proposer
   ↓
Acceptors

Learner

A node/process that learns the final chosen value.

Depending on the implementation, roles can sometimes be combined.

---

7. Paxos as a Form of Distributed Master Election

Paxos can also be used to elect a master.

Imagine every node writes its own name:

Node A → "A"
Node B → "B"
Node C → "C"

If a node successfully establishes its value through consensus, it can become the master.

Conceptually:

Paxos
  ↓
Agreement
  ↓
One chosen value
  ↓
Master election

So Paxos can be viewed as a mechanism for achieving agreement on who/what should be selected.

---

8. Paxos vs Raft

Paxos

• Distributed consensus protocol

• Powerful but complicated

• Failure scenarios can be difficult to reason about

• Historically important and widely influential

Raft

Raft performs essentially the same fundamental job:

Distributed consensus.

But Raft was specifically designed to be easier to understand and implement.

A useful interview comparison:

Paxos	Raft
Consensus protocol	Consensus protocol
More difficult to understand	Designed for understandability
Complex failure scenarios	More structured approach
Historically influential	Easier to implement
Used as foundation in distributed systems	Used in many distributed systems

---

9. Paxos vs Blockchain Consensus

Traditional Paxos assumes something important:

Nodes are generally non-malicious.

They may:

• crash

• become unavailable

• experience network problems

But they are not deliberately trying to deceive the system.

Blockchain consensus is designed for a different environment where participants may be Byzantine/malicious.

For example:

Paxos
↓
Crash / failure tolerance
↓
Nodes generally cooperate

Whereas:

Blockchain / Byzantine consensus
↓
Some participants may lie
↓
System must still reach agreement

Bitcoin's consensus mechanism is therefore fundamentally different from ordinary crash-fault-tolerant consensus such as Paxos.

---

10. Paxos in Cassandra

A practical example is Cassandra Lightweight Transactions (LWT).

LWT provides conditional operations such as:

INSERT ... IF NOT EXISTS

Example:

Create username = "ramesh"
IF NOT EXISTS

Suppose two users simultaneously try to register:

User A → ramesh
User B → ramesh

Without coordination, both could potentially believe they succeeded.

Paxos-based coordination allows the system to establish:

ramesh → User A

and reject the conflicting operation.

Important distinction

Cassandra LWT is not the same as a traditional full database transaction such as:

BEGIN
   UPDATE...
   UPDATE...
   UPDATE...
COMMIT

Instead, it provides conditional/linearizable operations, typically within the relevant Cassandra partition.

---

11. Other Uses of Paxos

Paxos-style consensus can be used for:

• Leader/master election

• Distributed locking

• Distributed transaction coordination

• Replicated state machines

• Metadata agreement

• Coordination services

Examples mentioned in the lecture include systems such as:

• Cassandra Lightweight Transactions

• ClusterX-style distributed relational systems

• Google's Chubby coordination/lock service

---

12. The Most Important Concepts to Remember

1. Proposal number

Every proposal gets a unique, orderable number.

5 < 8 < 12

2. Prepare

Proposer asks:

"Will you promise not to accept anything below my proposal number?"

3. Promise

Acceptor says:

"I will not accept a lower proposal."

It does not necessarily mean it promises to accept the current proposal.

4. Quorum

The Proposer needs enough responses to make progress.

Majority / quorum

5. Accept Request

The Proposer asks Acceptors to accept the proposal/value.

6. Higher proposal wins

If an Acceptor has already seen a higher proposal, the lower proposal must yield.

7. Consensus

The final goal is:

Multiple nodes
      ↓
Agreement
      ↓
One consistent decision

---

13. Paxos in One-Line Interview Definition

Paxos is a distributed consensus protocol that enables a group of nodes to agree on a value despite node failures and unreliable communication, using ordered proposal numbers, promises, acceptances, and quorums.

---

🧠 Remember Paxos with this flow

CLIENT
   ↓
PROPOSER
   ↓
PREPARE
   ↓
PROMISE
   ↓
QUORUM
   ↓
ACCEPT REQUEST
   ↓
ACCEPTORS ACCEPT
   ↓
QUORUM
   ↓
VALUE CHOSEN

The golden rule:

Prepare → Promise → Accept → Accepted

And:

Higher proposal number always takes precedence over a lower proposal number.