PDF Publication Title:
Text from PDF Page: 072
72 3.12. MISCELLANEOUS Messages In this chapter so far, proposers in Classic Paxos sent their prepare and propose messages to all na acceptors and waited for a majority to respond. If all acceptors are up then this approach generates 2na messages per phase. This approach is taken by systems such as Chubby [Bur06], VRR [LC12, §4.1], Raft [OO14] and Moderately Complex Paxos [VRA15]. Since proposers need only a majority of acceptors to respond, they can safely just send messages to a majority of acceptors and send further messages only if needed, for example if one or more acceptors do not reply. In the best case, when all acceptors are up, this method generates 2(⌊na/2⌋ + 1) messages. If we wish to reduce the likelihood of needing to send further messages, we can send more than a majority in the first place. This is the approach taken in Ring Paxos [MPSP10, §4]. If we wish to minimise the number of messages further, we can have acceptors forward messages in a chain or ring. In the best case, this approach reduces messages to ⌊na/2⌋+2, however latency increases from 2 hops to ⌊na/2⌋ + 2 hops. This is similar to the approach taken in phase two of Ring Paxos [MPSP10, §3]. Stricter epoch conditions The Classic Paxos acceptor algorithm as described will promise/accept if a prepare/propose message has an epoch e greater than or equal to the last promised epoch epro. Some algorithms have stricter requirements such as [MPSP10, §4] which requires that e > epro to promise and Moderately Complex Paxos [VRA15] which requires both that e > epro to promise and e = epro to accept. These restrictions are always safe, as they are equivalent to dropping a message but may effect the liveness conditions for progress. Fail-stop model We could avoid writing to persistent storage by not permitting participants to restart after a failure. This would however mean that number of participants decreases over time and the system would need reconfiguration to maintain its fault tolerance. This is the approach taken by VRR [LC12, §4.3]. Alternatively, we could require that no more than a majority of acceptors fail [MPSP10, §4.2]. Virtual sequences When reaching consensus on a value as part of a sequence, it is useful to note that there is not necessarily a 1-to-1 correspondence between the values in the sequence and indexes used by the application. We can improve this by deciding at each index a sequence of values instead of a single value. This batching of values into decisions reduces decision latencyPDF 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 |