Distributed Consensus Algorithms

Distributed Consensus Algorithms

• Designed to allow a group of processes to reach an agreement
• Operate over unreliable communications networks

Consensus Definition

• Agreement on a single result among multiple participants
• Consensus is achieved once a majority of participants agrees on a proposal
• Reached consensus is eventually known by everyone
• Requires that the involved parties agree on any result, not just their preferred proposal
• Communication channels may be faulty, meaning messages can be lost

The Importance of Consensus

• Necessary to reliably reach agreement, even when failures occur
• Example: Ensures that a money transfer is fully completed, preventing loss of funds if a server fails mid-transaction

History of Consensus Research

• 1985: The FLP (Fisher-Lynch-Patterson) impossibility paper demonstrated that guaranteeing agreement in an asynchronous system is impossible if even one host may fail
• In synchronous settings, consensus is solvable as processes can proceed in simultaneous steps
• Synchronous solutions are resilient to faults, as they can be easily detected

Asynchronous Systems Defined

• No upper bound on processing time
• No upper bound on clock drift rate
• No upper bound on networking delay

FLP Impossibility Result

• In an asynchronous setting, no distributed algorithm can solve the consensus problem if even one processor might crash
• Failure detection is unreliable, making it impossible to distinguish between a slow host/network and a failed host

Types of Failures

• Non-Byzantine: Failed nodes stop communicating, aka "clean" or "fail-stop" failure
• Byzantine: Failed nodes continue sending messages that are incorrect or misleading, becoming a traitor

Asynchronous Non-Byzantine Model

• Assumption model which assumes that nodes will either work according to the prescribed algorithm or will simply fail

Consensus Goal

• Agreement between processes with mutable states
• Processes are concurrent, asynchronous, and failure-prone

Understanding Consensus Properties

• Liveness: Guarantees that something good will happen
  • Real-world Example: At least one athlete will win gold in the 100m final
  • Consensus Example: All processes decide a value
• Safety: Guarantees that something bad will never happen
  • Real-world Example: Peace treaty ensures war will not occur
  • Consensus Example: No two processes decide on different values

Paxos Protocols

• Is a set of protocols designed to achieve consensus in networks with unreliable processors
• Types include:
  • Basic Paxos
  • Multi-Paxos
  • Cheap Paxos
  • Fast Paxos
  • Byzantine Paxos
  • Generalized Paxos

Basic Paxos

• Key Features:
  • Invented by Laslie Lamport
  • Named after a Greek Island
  • Deterministic
  • Fault-tolerant
  • Guarantees consistent results

Does Paxos Solve Consensus?

• Provides safety and eventual liveness
  • Safety: Prevents choosing a value which has not been proposed
  • Liveness: Any proposals may eventually be chosen.
  • Only a single value can be chosen
  • A process never learns a value unless it was chosen
  • Guarantees consensus is eventually reached, though not guaranteed
• The FLP result means Paxos is not guaranteed to reach consensus, lacking a specific time bound

Agents in the basic Paxos Protocol

• Proposer: Receives requests from the client
  • Attempts to secure agreement from a quorum of acceptors
• Acceptor: Partakes in the maintenance of a distributed storage
  • A state change in a Paxos cluster only occurs when a majority of acceptors agree
• Learner: Learns the agreed-upon value
  • Can be queried to discover the consensus value

How Paxos Works in Practice

• Nodes take on multiple roles, including all of them
  • A node can send proposals, contribute to consensus, and learn the final agreed value
• Nodes must retain knowledge of what they have accepted
  • Prevents forgetting information even during communication faults
• A Paxos run aims at a single consensus
  • Reaching a consensus prevents further progress without initiating a new Paxos run

Multi-Phase Rounds

• Phase 1: Election of a leader
• Phase 2: Leader proposes a value, and processes acknowledge it
• Phase 3: Leader multicasts the final value

Phase 1: Election

• A potential leader selects a ballot identifier greater than any seen previously
• The leader then sends the ballot identifier to all processes
• Processes respond incorporating the highest ballot identifier they've seen
• Any process that receives a majority of OKs becomes the leader, otherwise restart

Phase 2: Proposal (Bill)

• The leader sends a newly proposed value to all participants unless some decided and sent you their value
• Recipient logs on disk and sends OK to the leader

Phase 3: Decision (Law)

• The leader forwards final decision to all participants if a majority of the nodes have responded with OK
• Log to disk

Consensus is Achieved When...

• When a majority of processes receive the agreed value and are in the process of logging to disk

Basic Paxos Protocol Steps

• Phase 1a: Prepare
  • The proposer selects a proposal number N and sends a prepare(N) request to a quorum of acceptors
• Phase 1b: Promise If the number (N) is greater than any previous promises or acceptances
  • The acceptor promises to not accept any future proposal less than N
  • The acceptor sends a promise(N, U) response
  • U is the highest-numbered proposal accepted so far
• Phase 2a: Accept! The proposer sends an accept(N, W) request to a quorum of acceptors after receiving respective promises
  • W is the value of the highest number proposal among the promise responses, or any value if there is no promise contained in any proposal
• Phase 2b: Accepted!
  • If N >= its number of any promise, the acceptor accepts proposal and notification to the learner

Milestones During These Phases

• Without a majority of acceptors promising, no ID less than IDp can succeed
• With majority agreement on a specific value, said consensus will always be on a single value
• With majority agreement on a specific IDp value, anyone can accept consensus and determine what that value will be

Problems During Liveness

• Process may fail. In this case as long as a majority of the processes are up it can continue
• The leader may fail. In this case start another round
• Messages may be delayed or dropped. In this case another round is started

Livelock in Paxos

• Is possible when two proposers propose conflicting/different values
• To solve this add an exponential back-off in place, to prevent any hot spots

Additional Considerations

• Acceptors may send "NACKs" responses if they are not going to accept a proposal, informing the proposer it's not going to work
• Proposal numbers need to be strictly increasing and globally unique
  • Achieve this by setting low-order bits to a proposer's ID