PDF Publication Title:
Text from PDF Page: 032
32 2.3. EXAMPLES or propose(e,v), must have an epoch e greater than or equal to epro to be processed by the acceptor (Algorithm 4, lines 4,8). If this is the first message the acceptor has received then epro is nil and this test is always successful. If the test is successful then epro is updated to e (Algorithm 4, lines 5,9). If the message was prepare(e), then the acceptor replies with promise(e,eacc,vacc) (Algo- rithm 4, line 6). If the acceptor has not yet accepted a proposal then eacc and vacc will be nil. When an acceptor sends a promise message, we say that the acceptor has promised epoch e13. If the message was propose(e,v) then the acceptor will set eacc and vacc to the proposal (e, v) (Algorithm 4, line 10) and reply with accept(e) (Algorithm 4, lines 11). In this case, we say that the acceptor has accepted the proposal (e, v). Definition 4. In Classic Paxos, a proposal (e, v) is decided if the proposal (e, v) has been accepted by the majority of acceptors. Note that this definition does not require that the proposal is still the last accepted proposal on a majority of acceptors. A value v ∈ V is said to be decided if there exists an epoch e ∈ E such the proposal (e, v) has been decided. This is also described as value v is decided in e. The commit point is the first time a proposal is decided. 2.3 Examples In this section, we will consider example message sequence diagrams (MSDs) for a sample of possible executions of Classic Paxos. For simplicity, messages are omitted if their receipt will have no effect. Each example system is comprised of three acceptors A = {a1, a2, a3} and two proposers P = {p1, p2}, thus ⌊na/2⌋ + 1 = 2. Initially, γ = A for proposer p1 and γ = B for proposer p2. In our examples, epochs are natural numbers E = N0, which have been divided round robin between the proposers. Therefore initially E = {0,2,4,...} on p1 and E = {1,3,5,...} on p2. Figure 2.2 gives an example of two proposers executing Classic Paxos in serial. Firstly, proposer p1 executes Classic Paxos and the proposal (0, A) is decided. Then proposer p2 executes Classic Paxos and the proposal (1,A) is decided. Both proposers are able to complete Classic Paxos in two phases. This represents the best case scenario for Classic Paxos. the state list for each algorithm only includes new variables. The descriptions of variables such as vacc can be found in Table 2.1. 13The term adopts is sometimes used in the literature instead of promised, for example in [VRA15]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 | RSS | AMP |