Chapter 8: Paxos

Question 1

Broader context

Answer 1

• Durably persists association of tables, tablets, storage units is compromised of a highly available & reliable service
• ZooKeeper (Chubby)
• Usually five distributed nodes

Question 2

Consensus problems

Answer 2

• Desire all processes to agree on a value after one or more processes proposed a value (here, value is update to mapping)
• Also known as problems of agreement
• Challenges
  
  • Reach consensus, even in the presence of failures
  • Tolerate crash failures

Question 3

Consensus problem examples

Answer 3

• Two armies decide consistently to attack or to retreat critical sector
• Mutual exclusion: Processes agree on who can enter CS
• Leader election: Processes agree on who is elected
• Totally ordered multicast: Processes agree on the order of messages delivered
• ATM and bank’s servers agree what should happen to bank account balance when withdrawing money
• Flight computers decide to “abort” (reboot) or “proceed”
• Transaction managers agree to commit or abort
• Reactor safety systems agree on position of control rods

Question 4

Paxos

Answer 4

• Family of protocols for solving consensus among unreliable processes
• Published in 1989 (initially), 1998 (ACM TOCS)
• Fictional legislative consensus system for the island of Paxos
• Consensus: Agreeing on one result among group of participants
• Participants and communication among participants may fail

Question 5

Paxos family

Answer 5

• Basic Paxos, Multi-Paxos, Cheap Paxos, Fast Paxos, Byzantine Paxos etc.
• Protocols with spectrum of trade-offs between
  
  • Number of processes
  • Number of message delays before learning the agreed value
  • Activity level of individual participants
  • Number of messages sent
  • Types of failures tolerated

Question 6

The FLP result

Answer 6

• Fischer, Lynch and Paterson, 1985
  
  • In asynchronous systems, with only one process crashing, there is no guarantee to reach consensus (No also that guumtas consensus )
• Does not mean that consensus can never be reached
• Just under the model’s assumptions, no algorithm can always reach consensus in bounded time

Question 7

Paxos in light of FLP result

Answer 7

• No deterministic fault-tolerant consensus protocol can guarantee progress in an asynchronous system
• Paxos guarantees safety, but not progress
• “Conditions that could prevent progress are difficult to provoke.”
• Paxos attempts to make progress even during periods when some bounded number of replicas are unresponsive

Question 8

Use of Paxos

Answer 8

• Used in one form or another inside
  
  • Google’s Chubby
  • Yahoo’s (Apache) ZooKeeper
• Used where durability is required
  
  • Replicate state
  • Replicate files, etc.
• Agree on value (command to execute)

Question 9

Assumptions

Answer 9

• Process
  
  • Operate at arbitrary speed
  • May experience failures
  • Processes with stable storage may re-join the protocol after failures (i.e., following a crash- recovery failure model)
  • Do not collude, lie, or otherwise attempt to subvert the protocol (i.e., no Byzantine failures, cf. Byzantine Paxos)
• Network
  
  • Processes can send messages to any other process
  • Messages are sent asynchronously (i.e., may take arbitrarily long)
  • Messages may be lost, reordered, or duplicated
  • Messages are delivered without corruption (i.e., no Byzantine failures, cf. Byzantine Paxos)
• Number
  
  • In general, Paxos can make progress using 2F+1 processes
  • Despite the simultaneous failure of any F processes (e.g., 5 processes, resilient against 2 failing) of processes
  *

Question 10

Roles

Answer 10

• Express protocol in terms of roles
• Single process may play one or more roles at the same time
• No effect on protocol correctness
• Roles are commonly coalesced to improve latency, number of messages exchanged, etc.
• Roles:
  
  • Client (Application)
  • Acceptor (Voters)
  • Proposer
  • Learner
  • Leader (one of the Proposer)

Question 11

Client

Answer 11

• A client is typically a system or a system component that requires reliable, system-wide storage of information
• Issues request/response to Paxos-based (distributed) system, e.g., a write request, the value V to be stored
• Examples:
  
  • Metadata (e.g., configuration of BigTable deployment in Chubby)
  • Locking information in distributed ME
  • Commands issued to replicated server

Question 12

Proposal number & agreed value

Answer 12

• Attempt to define an agreed value V via proposals
• Proposals may or may not be accepted by Acceptors
• Proposals are uniquely numbered for a given Proposer
• Value V represents the information that is to be agreed on (replicated and persisted)

Question 13

Proposer

Answer 13

• Advocates a client request, attempting to convince the Acceptors to agree on it
• Acts as a coordinator to move the protocol forward when conflicts occur
• Messages sent by Proposer (more details later):
  
  • prepare (P# (N))
  • acceptReq (P# (N), Value (V))
• where P# refers to the Proposal Number (cf. below)

Question 14

Acceptor (a.k.a. Voters)

Answer 14

• Act as the fault-tolerant“memory” of protocol
• Are collected into groups called quorums (essentially, a majority)
• Any message sent to Acceptor must be sent to a quorum of Acceptors
• Any message received from an Acceptor is ignored unless a copy is received from each Acceptor in a quorum en
• Messages sent by Acceptor (more details later):
  
  • promise (P#, old P# (N’), old Value (V’))
  • accepted (P#, V)
• where P# refers to the Proposal Number (cf. below)

Question 15

Learner

Answer 15

• Act as replication factor for the protocol
• Once a Client request has been agreed on by Acceptors, Learner may take action (i.e., execute request and send response)
• To improve availability, additional Learners may be added
• Messages sent by Learner:
  
  • clientRes (Value (V))

Question 16

Leader

Answer 16

• Paxos requires a distinguished Proposer, the Leader, to make progress
• Many processes may believe they are Leaders, but the protocol only guarantees progress if one of them is eventually chosen
• If two processes believe they are Leaders, they may stall the protocol by continuously proposing conflicting updates
• Safety properties are still preserved, even in this case

Question 17

Quorum

Answer 17

• Express safety properties of Paxos by ensuring at least some surviving processes retain knowledge of results
• Quorum is subset of set of Acceptors such that any two subsets (that is, any two quorums) share at least one member
• Typically, any majority of participating Acceptors
• Example:
  
  • Given Acceptors {A,B,C,D}
  • Majority quorum would be any three Acceptors:
    {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}

Question 18

Safety and liveness properties

Answer 18

• Non-triviality: Only proposed values can be learned
• Safety: At most one value can be learned (i.e., two different Learners cannot learn different values)
• Liveness: If value V has been proposed, then eventually Learner L will learn some value (if sufficient processes remain non-faulty)
• Paxos ensures safety property holds, regardless of the pattern of failures

Question 19

Basic Paxos

Answer 19

• Most basic Paxos protocol
• Each protocol invokation instance decides on a single output value
• Protocol may proceed over several rounds
• A successful round has two phases
  
  • Prepare and promise
  • Accept and accepted
• Proposer needs to communicate with at least a quorum of Acceptors (otherwise no need to run)

Question 20

Phases

Answer 20

• Phase 1: Message (Actor)
  
  • Prepare (Proposer) and Promise (Acceptors)
• Phase 2: Message (Actor)
  
  • Accept (Proposer) and Accepted (Acceptors)
• Initiation via client request
• Termination via response to client
• Learner receives the Accepted messages from Acceptors and responds to client

Question 21

Messages (Actor)

Answer 21

• Client Request (C):
  
  • clientReq(Value V)
• Prepare(P):
  
  • prepare(Proposal# N)
• Promise(A):
  
  • promise(Proposal# N, older Proposal# N’, older Value V’)
• AcceptRequest(P):
  
  • acceptReq(N, V)
• Accepted(A):
  
  • accepted(N, V)
• ClientResponse(L):
  
  • clientRes(Decided Value D)

Question 22

Phase 1a: Prepare (@ Proposers)

Answer 22

• A Proposer (Leader) creates proposal identified by proposal number N
• Number must be greater than any previous N’ by this Proposer
• Proposer sends a prepare message with N to quorum of Acceptors:
  
  • prepare(N)
• Proposer decides who (among the acceptors) is in the quorum

Question 23

Phase 1b: Promise (@ Acceptors)

Answer 23

• If N is higher than any previous N’ received from any Proposer by the Acceptor, then the Acceptor must return a promise to ignore all future proposals having a number less than N
  
  • promise(N, -, -)
• (HIGHER)
• If the Acceptor accepted a proposal at some point in this the past, it must include the previous N’ and previous value v’ in its response to the Proposer
  
  • promise(N, N’, v’)
• (LOWER)s
• • Otherwise, the Acceptor ignores the received proposal

Question 24

Phase 2a: Accept Request (@Proposer)

Answer 24

• If a Proposer receives enough promises from a quorum of Acceptors, it needs to set a value to its proposal
• If p# >
• If any Acceptors had previously accepted any proposal, then they’ll have sent their values to the Proposer, who now must set the value of its proposal to the value associated with the highest proposal number reported by the Acceptors
• If none of the Acceptors had accepted a proposal up to this point, then the Proposer may choose any value for its proposal
• Proposer sends an Accept Request message to a quorum of Acceptors with the chosen V (value) for its proposal
  
  • acceptReq(N, V)

Question 25

Phase 2b: Accepted (@Acceptor)

Answer 25

* If an **Acceptor receives an Accept Request message for a proposal number N**, **it must accept it _if and only if_ it has not already promised to only consider proposals having an identifier greater than N** * In this case, it registers the corresponding value V and sends an Accepted message to the Proposer and every Learner * **accept(N, V)** * Otherwise, it ignores the Accept Request * An **Acceptor can accept multiple proposals** * Paxos guarantees that the Acceptors ultimately agree on a single value * Rounds **fail** **when** **multiple** **Proposers** **send** **conflicting** **Prepare** **messages** * Rounds **fail** when Proposer does **not** receive a **quorum** of responses (Promise or Accepted) * In these cases, another round must be started with a higher proposal number

Question 26

Basic Paxos protocol timeline

Answer 26

Question 27

Failure scenarios

Answer 27

* **Failure of Acceptor** * **Failure of redundant Learner** * **Failure of Proposer** * **Dueling Proposers**

Question 28

Basic Paxos: Failure of Acceptor

Answer 28

Question 29

Failure of redundant Learner

Answer 29

Question 30

Basic Paxos: Failure of Proposer

Answer 30

Question 31

Dueling Proposers

Answer 31

Question 32

Summary

Answer 32

* Solving **consensus in asynchronous environment** among **unreliable** **processes** * **Paxos guarantees safety**, but **progress** **may** **not** **hold** * One basic Paxos protocol instance required to **agree** **on** a single value **V** * Value represents the command to be executed or the data to be persisted * Paxos is at the **heart of Internet-scale systems deployed by major players** * Paxos protocol family has many members; here, Basic Paxos was reviewed