PDF Publication Title:
Text from PDF Page: 026
26 2.1. PRELIMINARIES Safety Informally, we can see that this simple algorithm satisfies the three safety conditions for distributed consensus. The acceptor chooses the first proposal it receives thus it satisfies non-triviality. After accepting its first proposal, the acceptor accepts no other proposals from proposers thus this algorithm satisfies safety. If a proposer returns a value, then the value must have been received from the acceptor and therefore must be decided, satisfying safe learning. We will now consider these in more detail. Theorem 1 (Non-triviality of SAA). If the value v is decided, then v must have been proposed by a proposer Proof of theorem 1. Assume the value v is decided. For v to be decided, the acceptor must have accepted the proposal propose(v). Thus since messages cannot be corrupted, v must have been proposed by some proposer Theorem 2 (Safety & safe learning of SAA). For any two proposers p,p′ ∈ P, which learn that the decided value v is γ and γ′ respectively then γ = γ′. Proof of theorem 2. A proposer p learns that the decided value v is γ as a result of receiving accept(γ) from the single acceptor. The same is true for any other participant p′. Since the events of sending accept(γ) and sending accept(γ′) occur on one participant, the single acceptor, the two events cannot have occurred concurrently. Thus one event must happen before the other. Assume that the event send accept(γ) is before send accept(γ′). The acceptor determines the values γ, γ′ by reading the accepted value vacc. If γ ̸= γ′ then the value vacc would have changed from γ to γ′ between sending the two accepted messages. The only mechanism for the accepter to update vacc to γ′ is by receiving accept(γ′). Updating vacc is conditional on vacc being nil, since vacc is persistent, it cannot be nil as it has previously been set to γ. Therefore vacc cannot have been updated between the two sending events so γ = γ′. The same applies when send accept(γ′) is before send accept(γ). Progress Informally, we can see that this simple algorithm also satisfies the two progress conditions for distributed consensus, under the liveness conditions that the acceptor and at least one proposer must be up. Note, that though we use the assumption that messages are eventually delivered, we do not require time bounds on message delivery or operating speed.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 |