PDF Publication Title:
Text from PDF Page: 047
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 47 Note how these liveness conditions differ from the liveness conditions for SAA (§5). SAA requires that the single acceptor is up whereas Classic Paxos requires a majority of acceptors to be up. Classic Paxos, however, requires exactly one proposer is up, whereas SAA only requires that at least one proposer is up. Classic Paxos also requires bounds on execution time (for acceptors only) and message delay, unlike SAA which only requires eventual execution and message delivery. This proof of progress requires that proposers know the bounds δa, δm and δd. If the proposer does not wait long enough before retrying then the system may not make progress. If the bound is unknown, this can be addressed using backoff timers as new epochs are generated. 2.8 Summary Single-valued distributed consensus is the problem of deciding a single value between a set of participants. An algorithm is said to solve distributed consensus provided it guarantees safety, so that decisions are final and progress, so that eventually a decision will be reached. Algorithms operating in an asynchronous, unreliable distributed system cannot guarantee progress without assumptions regarding the liveness and/or synchrony of the system. Number of acceptors Conditions for progress: Number of live proposers Number of live acceptors Synchrony Number of messages Number of round trips Number of persistent writes SAA 1 1 or more All (1) no 2 1 1 Classic Paxos na exactly 1 ⌊na/2⌋ + 1 or more yes 2na+2ormore 2 or more 3 or more Table 2.4: Comparison between SAA & Classic Paxos This chapter introduced two known distributed algorithms: the Single acceptor algorithm (SAA) and Classic Paxos. Both algorithms guarantee safety and progress thus both solve distributed consensus, however, their liveness conditions for progress differ. Both algorithms divide participants in a system into proposers, which propose values to be decided and acceptors, which choose and store values. SAA requires that the single acceptor and at least one proposer are live. Classic Paxos requires that a strict majority of acceptors and exactly one proposer is live and that these participants are operating synchronously. Under these conditions, a proposer in SAA is guaranteed to terminate in one round trip to the acceptor, whereas, a proposer in Classic Paxos is guaranteed to terminate in a finitePDF 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 |