Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 11

Let = r1 , and let L = 1. Validity is easy: a process decides 1 only if there issome 1-input if all messages are delivered, and all inputs are 1, then the protocol will decide1. The more interesting part here is agreement. Fix a particular adversary. If all messagesare delivered, then the protocol will have all processes decide on the same value. We nowfocus on the case that some message is not delivered, and let k denote the rst round atwhich a message is lost.Claim 2 The only case in which there is disagreement is where key = k.Proof: We use the fact that if either process receives green messages for at least l rounds,then the other does for at least l ; 1 rounds.If k < key , then one process fails to receive a green message at some round strictly beforethe kth round. Consequently, the other fails to do so by round k + 1 key , and by theprotocol, neither attacks.If k > key then both get at least key green messages.

Also, since this means k > 1, bothknow value of key , and both know same initial values, and thus they decide on the samevalue.51Corollary 3 Let A be any adversary, and let r be the number of rounds. ThenPrA disagreement] 1rAn Upper Bound on the Liveness. An obvious question that arises after the 2-processoralgorithm is can we do better?Before giving an answer, we observe that the algorithm above has the unpleasant propertythat if just one rst-round message gets lost, then we are very likely not to attack. Wemight be interested in improving the probability of attacking as a function of the numberof messages that get through, aiming at a more rened liveness claim.

Another directionof improvement is to extend the algorithm to arbitrary graphs, since the 1-round dierenceclaimed above does not always hold in general graphs. Therefore, the answer to the questionabove is yes, we can give a modication for more general graphs that has provably betterliveness bounds for partial message loss.

On the other hand, however, an almost-matchingupper bound for the liveness we prove below shows we cannot do signicantly better.We start with a denition of a notion that is important the impossibility proof and in theextended algorithm we shall describe later. We dene the \information level" of a processat a given time-point. This notion will be used instead of the simple count of the number ofconsecutive messages received.Denition 3 Let i 2 V be a process, and let k be a round number. Fix an adversary A.

Wedene HA (i k), the set of heights of i at round k inductively as follows.1. 0 is an element of HA (i k).2. 1 is an element of HA (i k ) if at round k , process i knows about some initial value of 1.3. h > 1 is an element of HA (i k) if at round k , for all processes j 6= i, process i knowsthat h ; 1 2 HA (j l) for some l.Finally, dene level A(i k ) = max HA (i k).Intuitively, level A(i k) = h means that at round k, processor i knows that all processorsknow that all processors know ... (h times) ... that there exists an input value 1. As it turnsout, this level plays a key role in the randomized consensus probability bounds.We can now prove the upper bound on the liveness.Theorem 4 Any r-round protocol for the generals problem with probability of disagreementat most and probability of attack (when no message is lost) at least L satisesL (r + 1) :52We prove Theorem 4 using the following more general lemma.Lemma 5 Let A be any adversary, and let i 2 V be any node.

ThenPrA i decides 1] level A (i r)We rst show how the lemma implies the theorem.Proof: (of Theorem 4).For the liveness condition, we need to consider the adversary A in which all processors haveinput 1 and no messages are lost. The probability that all processors decide 1 is at most theprobability that any of them decides 1, which is, by Lemma 5, at most level A(i r), andsince by the denition of A, level A (i r) r + 1, we are done.We now prove the lemma.Proof: (of Lemma 5).First, based on A, we dene another adversary A0 as follows.

A0 is the adversary in whichthe only initial values of 1 and the only messages delivered, are those that i knows about inA. Put in the execution graph language, A0 is obtained from A by modifying the executionas follows. We remove all the edges (i.e., messages) which are not on a path leading to anynode associated with process i we also change the inputs in the initial states from 1 to 0for all the initial states from which there is no path to any node associated with i. The ideain A0 is to change all the 1 inputs that are \hidden" from i in A to 0, while preserving the\view" from process i's standpoint.Now we can prove the lemma by induction on the value of level A (i r).Base: Suppose level A (i r) = 0. Then in A, i doesn't know about any initial 1 value, andhence in A0, all the initial values are 0.

By validity, i must decide 0, and since A i A0, weconclude that i decides 0 in A as well.Inductive step: Suppose level A(i r) = l > 0, and suppose the lemma holds for all levelsless than l. Consider the adversary A0 dened above. Notice that there must exist some jsuch that level A (j r) l ; 1: otherwise, we would have level A(i r) > l, a contradiction.Now, by the inductive hypothesis,0PrA j decides 1] level A (j r)00and hencePrA j decides 1] (l ; 1)But by the agreement bound, we must have0PrA i decides 1] PrA j decides 1] + 0053and thusPrA i decides 1] l0and since A i A0, we may conclude thatPrA i decides 1] lExtended Algorithm.

The proof of Theorem 4 actually suggests a modied algorithm,which works in arbitrary connected graphs. Roughly speaking, the processes will computetheir information levels explicitly, and will use this information level in place of the numberof consecutive message deliveries in a threshold-based algorithm. As in the basic algorithm,process 1 still needs to choose key at the rst round, to be used as a threshold for the levelreached. To get any desired 1 ; probability of agreement, we now let key be a real chosenuniformly from the interval 0 1=].We extend the denition of level slightly to incorporate knowledge of the key , as follows.Denition 4 Let i 2 V be a process, and let k be a round number.

Fix an adversary A. Wedene HA0 (i k), the set of heights of i at round k inductively as follows.1. 0 is an element of HA0 (i k).2. 1 is an element of HA0 (i k ) if at round k, process i knows about some initial 1-value,and knows key.3. h > 1 is an element of HA0 (i k) if at round k , for all processes j 6= i, process i knowsthat h ; 1 2 HA (j l) for some l.Dene the modied level by mlevel A(i k) = max HA0 (i k ).The dierence from Denition 3 is in (2) | we require that the knowledge containthe value of key also. It is not hard to show that mlevel is always within one of level (cf.homework problem). The idea in the protocol is simply to calculate the value of mlevel A (i k)explicitly.Each process maintains a variable mlevel , which is broadcast in every round.The processes update mlevel according to Denition 4.

After r rounds, a processdecides 1 exactly if it knows the value of key , and its calculated mlevel is at leastkey .54Analysis. For simplicity, we will just carry out the analysis assuming that the graph Gis complete. Modications for other graphs are left as an exercise.First, consider the validity condition. If all processes start with 0, then mlevel remains 0at all processors throughout the execution, and so they all decide 0.Lemma 6 Assume the graph is complete. If all processes start with 1 and no message islost, thenPr attack] min(1 r)Proof: If all processes start with 1 and no message is lost, then by the end of the algo-rithm mlevel r everywhere, and the probability L of all attacking is at least equal to theprobability that r key .

If r 1 , then Pr attack] = 1. If r < 1 , then Pr attack] = r1 = r.We remark that it is possible to get a more rened result, for intermediate adversaries:for any given adversary A, dene L(A) to be the probability of attack under A, and mlevel Ato be the minimum value of mlevel A (i r), i.e., the minimum value of the mlevel at the endof the protocol, taken over all the processes. Then L(A) min(1 mlevel A ).

The proof isleft as a simple exercise.We now analyze the agreement achieved by the protocol. (This does not depend on thegraph being complete.)Lemma 7 Let A be any adversary. Then the probability of disagreement under A is no morethan .Proof: By the protocol, if mlevel A key then all processes will attack, and if mlevel A <key ; 1 then all processes will refrain from attacking. This follows from the fact that thenal mlevel values are within 1 of each other. Hence, disagreement is possible only whenmlevel A key mlevel A +1.