Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Distributed Systems > Chapter 8: Paxos > Flashcards

Chapter 8: Paxos Flashcards

1
Q

Broader context

A
  • Durably persists association of tables, tablets, storage units is compromised of a highly available & reliable service
  • ZooKeeper (Chubby)
  • Usually five distributed nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Consensus problems

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Consensus problem examples

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Paxos

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Paxos family

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

The FLP result

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Paxos in light of FLP result

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Use of Paxos

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Assumptions

A
  • 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
    *
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Roles

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Client

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Proposal number & agreed value

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Proposer

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Acceptor (a.k.a. Voters)

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Learner

A
  • 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))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Leader

A
  • 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
17
Q

Quorum

A
  • 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}
18
Q

Safety and liveness properties

A
  • 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
19
Q

Basic Paxos

A
  • 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)
20
Q

Phases

A
  • 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
21
Q

Messages (Actor)

A
  • 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)
22
Q

Phase 1a: Prepare (@ Proposers)

A
  • 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
23
Q

Phase 1b: Promise (@ Acceptors)

A
  • 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
24
Q

Phase 2a: Accept Request (@Proposer)

A
  • 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)
25
Q

Phase 2b: Accepted (@Acceptor)

A
  • 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
26
Q

Basic Paxos protocol timeline

A
27
Q

Failure scenarios

A
  • Failure of Acceptor
  • Failure of redundant Learner
  • Failure of Proposer
  • Dueling Proposers
28
Q

Basic Paxos: Failure of Acceptor

A
29
Q

Failure of redundant Learner

A
30
Q

Basic Paxos: Failure of Proposer

A
31
Q

Dueling Proposers

A
32
Q

Summary

A
  • 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

Distributed Systems (21 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions