Paxos ./~course/cs501/2012 Hongfei Yan School of EECS, Peking University 5 /2/2012 Some Slides borrow from Idit Keidar Terminology ? Consensus , the problem of a number of processes trying to agree on mon decision – leader, state machine replication, and atomic broadcasts. ? Failure detectors , as a mechanism for solving consensus in an asynchronous message-passing system 23 Material ? Paxos Made Simple Leslie Lamport ACM SIGACT News (Distributed Computing Column) 32 , 4 (Whole Number 121, December 2001) 18-25. Paxos ‘ s notation ? Classes of agents: – Proposers – Acceptors – Learners ? A node can act as more than one clients (usually 3). Paxos algorithm ? Phase 1 (prepare): – A proposer selects a proposal number n and sends a prepare request with number n to majority of acceptors. – If an acceptor receives a prepare request with number n greater than that of any prepare request it saw, it responses YES to that request with a promise not to accept any more proposals numbered less than n and include the highest- numbered proposal (if any) that it has accepted. Paxos algorithm ? Phase 2 (accept): – If the proposer receives a response YES to its prepare requests from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a values v which is the value of the highest- numbered proposal among the responses. – If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n. Definition of chosen ? A value is chosen at proposal number n iff majority of acceptor accept that value in phase 2 of the proposal number. Paxos ’ s properties ? P1: Any proposal number is unique. ? P2: Any two set of acceptors have at least one acceptor mon. ? P3: the value sent out in phase 2 is the value of the highest-numbered proposal of all the responses in phase 1. Proof of saf
