PDF Publication Title:
Text from PDF Page: 078
78 4.2. QUORUM INTERSECTION ACROSS EPOCHS and by the requirement that any two quorums will intersect. We can however also prove lemma 11 using the weaker revision A quorum intersection from equation 4.4: Revised proof of lemma 11. Assume the value v is decided in epoch e, thus some phase two quorum of acceptors Q2 ∈ Q2 would have accepted the proposal (e, v). Before a value is proposed in phase two, a phase one quorum Q1 ∈ Q1 of acceptors must promise to the proposer (Property 11). From equation 4.4, these two quorums will always intersect therefore the quorums will always have at least one acceptor in common. The proof of lemma 11 was the only occasion that quorum intersection was utilised in the proof of Classic Paxos. Therefore, we can substitute the above into the original proof of Classic Paxos, for proof of safety for Paxos revision A. For the sake of brevity, we do not reproduce the full proof here. The proof of non-triviality for Classic Paxos (§2.5) did not utilise quorum intersection and therefore still applies for Paxos Revisions A. 4.1.3 Examples Figures 4.1 and 4.2 illustrate two example executions of Paxos revision A. In both cases, the system is comprised of four acceptors A = {a1, a2, a3, a4} and two proposers P = {p1, p2}. The quorum system is as follows: Q1 = {{a1, a2}, {a3, a4}} and Q2 = {{a1, a3}, {a2, a4}}. This quorum system has been chosen as it has the minimum intersection to satisfy the revised quorum intersection requirements. For simplicity, the acceptors in this example only send messages to one quorum for each phase instead of all possible quorums. Figure 4.1 shows the two proposers executing Paxos revision A in serial. Proposer p1 decides the proposal (0, A) prior to proposer p2 starting the proposer algorithm. As expected, the proposer p2 decides the proposal (1,A). Figure 4.2 shows the two proposers executing Paxos revision A concurrently. Both proposers are able to complete phase one as the two phase one quorums used are disjoint. However, only p2 is able to complete phase two due to the intersection between p1’s phase two quorum and p2’s phase one quorum at acceptor a3. Proposer p1 subsequently retries with epoch 2 and (2,B) is decided. 4.2 Quorum intersection across epochs In the previous section, we differentiated between the quorums for each phase of Paxos. We continue this refinement by differentiating between the quorums by their associated epochs, e ∈ E as well as their phase. We use Qen to denote the quorum set for phase n with epoch e. Thus far we have used the same quorum set regardless of the epoch. If we used epoch specific quorums sets, we would require the following for each epoch e: ∀Q∈Qe1,∀f ∈E,∀Q′ ∈Qf2 :Q∩Q′ ̸=∅ (4.5)PDF 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 (Standard Web Page)