PDF Publication Title:
Text from PDF Page: 027
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 27 Theorem 3 (Progress of SAA). If a proposer p ∈ P proposes the value γ and the liveness conditions are satisfied for a sufficient period then a value v is eventually decided. Proof of theorem 2. Assume proposer p sends propose(γ) to the acceptor. Under the live- ness conditions, this message will be eventually received by the acceptor. Under the liveness conditions, this acceptor must be up and handle the message. Either no decision has yet been reached thus the proposal is accepted and v = γ, otherwise a decision has already been reached and v = vacc. Summary This simple algorithm provides consensus in one round trip (two messages) to the acceptor and one synchronous write to persistent storage, provided the acceptor is up. If the acceptor is down, then the system cannot progress until the acceptor is up. This algorithm works as all value proposals intersect at a single point, the acceptor. The result is that proposals are totally ordered so choosing a proposal is trivial. However, this reliance on a single acceptor is also this algorithm’s downfall. Should this acceptor fail, the algorithm could not make progress until it recovers. The acceptor in SAA is a single point of failure, the obvious step to address this is to have multiple acceptors. However, we can no longer guarantee a total ordering over proposals so the single acceptor algorithm is no longer suitable6. In the next section, we instead describe Classic Paxos, a consensus algorithm which is able to handle multiple acceptors. 2.2 Classic Paxos Classic Paxos [Lam98]7 is an algorithm8 for solving the problem of distributed consensus. In the best case, the unoptimised algorithm is able to reach agreement in two round trips to the majority of acceptors and three synchronous writes to persistent storage, though in some cases more time will be needed. The liveness conditions is that ⌊na/2⌋ + 1 of na acceptors and one proposer must be up and communicating synchronously. These conditions are both necessary and sufficient for progress. The approach taken by Classic Paxos to deciding a value has two phases. Phase one can be viewed as the reading phase, where the proposer learns about the current state of the system and takes a type of version number to detect changes in the future. Phase two can be viewed as the writing phase, where the proposer tries to get a value accepted. If, after phase one of the algorithm, the proposer is certain that a value has not yet been decided, 6Assuming the network does not provide atomic broadcast. 7Also known as Synod or Single-degree Paxos 8More correctly, it is a family of algorithmsPDF Image | Distributed consensus
PDF Search Title:
Distributed consensusOriginal File Name Searched:
UCAM-CL-TR-935.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |