Distributed Consensus Algorithms

Distributed Consensus Algorithms

• Distributed consensus algorithms handle reaching agreements among a group of processes
• The processes are connected by unreliable communications networks

Consensus

• Consensus involves agreeing on one result
• Consensus occurs once a majority agrees on a proposal
• This consensus can become known to everyone eventually
• All parties involved should want to agree on any result
• Communication channels may be faulty, meaning that messages might get lost

Why Consensus Matters

• To reliably reach agreements, even in the presence of failures
• For example, if a money transfer goes out of one account but does not arrive at the destination account, this impacts reliability

History of Consensus

• 1985: The FLP (Fisher-Lynch-Patterson) impossibility paper was published
• Agreement cannot be guaranteed in an asynchronous system, even if only one host fails
• Consensus was known to be solvable in a synchronous setting, where processes proceed in simultaneous steps
• Synchronous solutions are resilient to faults since they could be easily detected
• Asynchronous refers to:
  • The lack of an upper bound on processing time
  • The lack of an upper bound on clock drift rate
  • The lack of an upper bound on networking delay
• Failures cannot be reliably detected due to asynchronicity
• The difference between slow hosts/networks and failed hosts cannot be known for sure
• The FLP result indicates that there is no distributed algorithm that solves the consensus problem in an asynchronous setting where only one processor might crash
• 1989: Lamport publishes The Part-Time Parliament
• Distributed systems are becoming more important because of the Internet

Types of Failures

• Non-Byzantine:
  • Failed nodes stop communicating
  • This is considered a "clean" failure
  • This is also known as fail-stop behavior
• Byzantine:
  • Failed nodes continue sending messages
  • These messages are incorrect or potentially misleading
  • The failed node becomes a traitor
• Byzantine failures are arbitrary deviations of a process from its expected behavior due to, for example, software bugs, hardware malfunctions, or malicious attacks
• Generally assumes an asynchronous, non-Byzantine model

Consensus Goals

• Agreement between processes with mutable states
• Processes are concurrent, asynchronous, and failure-prone
• Consensus equals making a decision (liveness) which is also correct (safety)

Liveness & Safety

• Liveness: guarantees that something good will happen
  • For example, a consensus of all processes decide a value
• Safety: guarantees that something bad will never happen
  • For example, consensus makes sure there is no potential for processes deciding a different value by reaching an agreement

Paxos

• Paxos is a family of protocols for solving consensus in a network of unreliable processors
• Basic Paxos, Multi-Paxos, Cheap Paxos, Fast Paxos, Byzantine Paxos, and Generalized Paxos are all part of the same family

Basic Paxos

• By Laslie Lamport, one of the initial core developers of LaTeX
• Considered a deterministic and fault tolerant consensus protocol
• Named after a Greek Island
• Guarantees consistent results
• It provides safety and eventual liveness
  • Regarding safety, only a value that has been proposed can be chosen
  • Only a single value can be chosen within a safe system
  • A process will never learn a value unless it was chosen
• Regarding eventual liveness, consensus will be reached at some point in the future, if things go well. However, this is not guaranteed
• The FLP result still applies since Paxos is not guaranteed to reach consensus
• There is no time bound
• It is still an eventual liveness

Analogy

• A part-time parliament
• Each round has three phases:
  • Phase 1: A leader is elected
  • Phase 2: The leader proposes a value (bill), processes acknowledgements
  • Phase 3: The leader multicasts the final value (law)

Agent Roles

• Proposer: receives a request from the client and tries to get acceptors to agree on it
• Acceptor: maintains the distributed storage
  • A state change in a Paxos cluster will not occur until a majority of acceptors agree upon it
• Learner: learns the agreed upon value and can be queried to know the consensus value

Practical Notes

• Paxos nodes can take multiple roles, even all of them
• A single node can send proposals to other nodes, contribute to consensus, and learn the final agreed upon value
• Paxos nodes must know how many acceptors are in a majority
• Paxos nodes must be persistent, and cannot forget what they accepted
• A Paxos run aims at finding a single consensus
• A consensus has to be reached before progressing
• To reach another consensus, a different Paxos run has to happen

Phases

• Rounds are asynchronous (no time synchronization required)
• If in round j and a message is heard from round j+1, abort everything and move to round j+1
• Each round has three phases
  • Phase 1: A leader is elected
  • Phase 2: The leader proposes a value (bill), processes acknowledgements
  • Phase 3: The leader multicasts the final value (law)

Phase 1 - Election

• A potential leader chooses a unique ballot ID, higher than any ID it has seen
• The ballot ID is sent to all processes
• Processes respond to the highest ballot ID
• A leader has to respond with OK if it's the majority
• Initiate a new round if there is no response from the majority

Phase 2 - Proposal

• The leader sends the proposal to everyone
• Use v=v' if a process already decided in a previous round
• If something is not proposed, then propose its value

Phase 3 - Decision

• If the leader hears Oks from the majority, the decision is sent to everyone else
• The consensus has been achieved when the majority processes hear and accept the proposed value
• If the process reaches it's OK response, then the system should have consensus
• Processes or even the leader may not be aware of the consensus
• If leader fails, at the point of the OK response, then it does not matter as there system is now consensus

Basic Paxos Protocol Details

• Phase 1a: Prepare Proposer selects a proposal number N and sends a prepare(N) request to a quorum of acceptors
• Phase 1b: Promise
  • If N is greater than the number of any previous promises or acceptances:
    • Promise to never accept any future proposal less than N
    • Send a promise(N, U) response, where U is the highest-numbered proposal accepted so far (if any)
• Phase 2a: Accept!
  • If proposer received promise responses from a quorum, it sends an accept(N, W) request to those acceptors
  • In this case, W is the value of the highest-numbered proposal among the promise responses or any value if no promise contained a proposal
• Phase 2b: Accepted
  • If N is greater or equal to the number of any previous promise:
    • Accept the proposal
    • Send an accepted notification to the learner

Milestones

• If the majority of acceptors promise, no ID lower than IDp can make it through
• If a majority of acceptors accept (IDp, value), consensus is reached
• If a proposer/learner gets the majority of accepts for a specific IDp, they know that consensus has been reached

Potential Issues

• Process fails, however, it should work as long as the majority is up
• Leader fails, another round can be set
• Message is dropped, if the system becomes flaky then another round can be initialized
• Another issue revolves around 2 or more proposers/leaders
• It can stall the Paxos run, A solution is to set an exponential back off in place
• Acceptors may send "NACKs" to state that they are not going to accept the given proposal Tick: setting strict lower-order bits to the proposer’s server ID