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

Now we can remove the rst-round message from p1 to q, and these two executionswill only look dierent to p1 and q. Now we replace second-round messages from q one-byone until we have an execution in which p1 does not send to q in the rst round and q sendsto all in the second round. This achieves our goal of removing a rst-round message from p1to q while still letting each consecutive pair of executions look the same to some nonfaultyprocess.In this way, we can remove rst-round messages from p1 one-by-one until p1 sends nomessages. Then we can change p1's input from 0 to 1 as before, and replace p1's messagesone-by-one.

Repeating this for p2,: : : ,pn gives the desired chain.The General Case. The preceding two examples contain the main ideas for the generalcase, in which there are up to f faulty processes in a run. Suppose we have an f roundprotocol for f faults.A little notation may help. If and 0 are runs with p nonfaulty in both then we write p 0 to mean that exec() and exec(0) look the same to p through time f (same statesequence and same messages received).We write 0 if there exists a process p that is nonfaulty in both and 0 such thatp 0 . We write 0 for the transitive closure of the relation.Every run has a decision value denoted by dec(). If 0 then dec() = dec(0) since and 0 look the same to some nonfaulty process.

Thus if 0 then dec() = dec(0).Now let F be the set of failures in run .80Lemma 5 Let and 0 be runs. Let p be a process. Let k be such that 0 k f ; 1. Ifand and 0 only dier in p's failure behavior after time k then 0 .(This means that the patterns are the same, except for some dierences in the existenceof some outgoing messages from p at rounds k + 1 or greater.)To get our result we need to use the case k = 0 in Lemma 5.

This says that if runs and0 have only one failure between them and dier only in the failure behavior of one processthen 0. We use this as follows.Let 0 and 00 be two runs both starting with all 0's as input in 0 no process fails, andin 00, process p1 fails at the beginning and sends no messages. There is only one failurebetween them and they only dier in p1 's failure behavior only, so by the lemma, 0 00.Now let 000 be the same as 00 except p1 has a 1 as input instead of 0. Since p1 sends nomessages in 00 this change cannot be seen by any process except p1, so 00 000 . Now let 1have the same input as 000 except there are no failures in 1.

Again the lemma says 000 1.Therefore 0 1.We continue this, letting i be the execution with no failures and input dened by havingthe rst i processes get 1 as input and the others get 0. We have i;1 i, so 0 n , andtherefore dec(0) = dec(n ). But this is a contradiction since 0 has all zeros as input withno failures and hence must decide 0 whereas n has all ones as input with no failures andhence must decide 1.It remains to prove the lemma. This will be done in the next lecture.jF F j k + 10816.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchOctober 1, 1992Lecture 77.1 Number of Rounds With Stopping Failures (cont.)Last time, we were showing the lower bound of f + 1 rounds on consensus with stopping.We had gotten it down to the following lemma.

Today we will nish by proving the lemma.Lemma 1 Let and 0 be runs. Let p be a process. Let k be such that 0 k f ; 1. IfjF F j k + 1 and and 0 only dier in p's failure behavior after time k then 0 .Intuitively, the lemma means that the patterns are the same, except for some dierencesin the outgoing messages from p at round k + 1 or later.Proof: We prove the lemma by reverse induction on k, i.e., k goes from f ; 1 down to 0.Base case: Suppose k = f ; 1. In this case and 0 agree up to the end of round f ; 1.Consider round f . If and 0 do not dier at all then we are done, so suppose they dier.Then p is faulty in at least one of or 0, and the total number of other processes that failin either or 0 is no more than f ; 1.

Consider two processes, q and r, that are nonfaultyin both and 0. Note that such two processes exist since n f + 2.Let 1 be the same as , except that p sends to q in round f of 1 exactly if it does in 0(see Figure 7.1 for example).We have r 1 and 1 q 0, so 0.Inductive step: We want to show that the lemma is true for k , where 0 k < f ; 1,assuming that it holds for k + 1. Runs and 0 agree up to the end of round k.

If they alsoagree up to end of round k + 1 then we can apply the inductive hypothesis and we are done,so assume process p fails in round k + 1, and assume (without loss of generality) that p failsin .Let i, for 1 i n, be the same as except that p sends to p1 ,: : : ,pi at round k + 1 ofi exactly if it does in 0.Claim 2 For 1 i n, i;1 i (where 0 = ).Proof: Executions i;1 and i dier at most in what p sends to pi at round k + 1. Let 0ibe the same as i;1 except that pi sends no messages after round k + 1 in 0i. Similarly let 00i082pHA HA HHHHAAAAAAAAAAppHAJ HAJ HHHHAJAJAJAJA JA JA JAAArqs1ppHJHJ HHHHJJJJJJJrqsprqs0Figure 7.1: Example of construction used to prove base case of Lemma 1.be the same as i except that pi sends no messages after round k + 1 in 00i .

This situationis illustrated in Figure 7.2.pp@@@@@;;@;i H@HH@@pi;1p@p@@@@i@ppi0i00ipi;;;H@HH@@iFigure 7.2: Example of construction used to prove inductive step of Lemma 1.Notice that each of i 0i 0i has no more than k + 2 failures (since has no more thank + 1 failures). Therefore, by the inductive hypothesis, we have i;1 0i and i 00i . Also0i 00i since both look the same to any nonfaulty process other than pi.

Thus i;1 i.From the claim, and by the transitivity of , we have = 0 n , and since n and 0 onlydier in p's failure behavior after time k + 1, we can apply the inductive hypothesis onceagain to get n 0. Thus we have 0, as needed.Applying Lemma 1 with k = 0, we can summarize with the following theorem.Theorem 3 Any agreement protocol that tolerates f stopping failures requires f +1 rounds.837.2 The Commit ProblemThe commit problem Dwork, Skeen] is a variant of the consensus problem, and may bedescribed as follows.

We assume that the communication is realized by a complete graph.We assume reliable message delivery, but there may be any number of process stoppingfaults.Agreement: There is at most one decision value.Validity:1. If any process starts with 0, then 0 is the only possible decision value.2. If all start with 1 and there are no failures, then 1 is the only possible decisionvalue.Termination: This comes in two avors.

The weak termination requirement is that termination is required only in the case where there are no failures the strong terminationrequirement species that all nonfaulty processes terminate.The main dierences between the between the commit problem and the consensus problem for stopping faults are, rst, in the particular choice of validity condition, and second,in the consideration of a weaker notion of termination.7.2.1 Two Phase Commit (2PC)For weak termination, the standard algorithm in practice is two-phase commit.

The protocolconsists of everyone sending their values to a distinguished process, say p1, p1 deciding basedon whether or not anyone has an initial 0 value, and broadcasting the decision (see Figure7.3 for illustration).p1Figure 7.3: message pattern in two-phase-commit protocolIt is easy to see that 2PC satises agreement, validity, and weak termination.84However, 2PC does not satisfy strong termination, because if p1 fails, the other processesnever nish.

In practice, if p1 fails, then the others can carry out some kind of communicationamong themselves, and may sometimes manage to complete the protocol.But this does not always lead to termination, since the other processes might not be ableto gure out what a failed p1 has already decided, yet they must not disagree with it. Forexample, suppose that all processes except for p1 start with 1, but p1 fails before sendingany messages to anyone else. Then no one else ever learns p1's initial value, so they cannotdecide 1. But neither can they decide 0, since as far as they can tell, p1 might have alreadydecided 1.This protocol takes only 2 rounds.

The weaker termination condition, however, impliesthat this does not violate the lower bound just proved on the number of rounds. (Note thatthe earlier result could be modied to use the commit validity condition.)7.2.2 Three-phase Commit (3PC)2PC can be augmented to ensure strong termination.

The key is that p1 does not decide tocommit unless everyone else knows that it intends to. This is implemented using an extra\phase". The algorithm proceeds in four rounds as follows (see also Figure 7.4).Round 1: All processes send their values to p1 . If p1 receives any 0, or doesn't hear fromsome process, then p1 decides 0. Otherwise, it doesn't yet decide.Round 2: If p1 decided 0, it broadcasts this decision.

If not (that is, it has received 1'sfrom everyone), then p1 sends tentative 1 to all other processes. If a process pi, i 6= 1,receives 0, it decides 0. If it receives tentative 1, it records this fact, thus removing itsuncertainty about the existence of any initial 0's, and about p1's intended decision.Round 3: If a process pi , i 6= 1 recorded a tentative 1, it sends ack to p1 . At the end ofthis round, process p1 decides 1 (whether or not it receives ack s from all the others).Note that p1 knows that each process has either recorded the tentative 1, or else hasfailed without deciding and can therefore be ignored.Round 4: If p1 decided 1, it broadcasts 1. Anyone who receives 1 decides 1.Rounds 2 and 3 serve as an extra phase of informing everyone of the \intention tocommit", and making sure they know this intention, before p1 actually commits.4Note that there is an apparent redundancy in this presentation.

It appears that the ack s, which arisein the practical versions of the protocol, are ignored in this abstract version. So this version can apparentlybe shortened to three rounds, eliminating the ack s entirely. This remains to be worked out.485prounds:11234Figure 7.4: message pattern in three-phase-commit protocolThis protocol does not guarantee strong termination yet. If p1 doesn't fail, every nonfaulty process will eventually decide, since p1 never blocks waiting for the others.