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

Thus, we have reached a contradiction. It follows that we cannot solve Byzantineagreement for conn(G) 2 and f = 1.To generalize the result to f > 1, we use the same diagrams, with q and s replaced bygraphs of at most f nodes each and p and r by arbitrary graphs. Again, removing q and sdisconnects p and r. The edges of Figure 6.2 now represent bundles of all the edges betweenthe dierent groups of nodes in p, q, r and s.756.3 Weak Byzantine AgreementA slightly stronger result that can be obtained from the same proof method.

Lamportdened a weaker problem than Byzantine agreement, still in the case of Byzantine faults, bychanging the validity requirement.Validity: If all processes start with value v and no faults occur, then v is the onlyallowable decision value.Previously we required that even if there were faults, if all nonfaulty processes startedwith v then all nonfaulty processes must decide v. Now they are only required to decide vin the case of no failures. This weakened restriction is motivated loosely by the databasecommit problem since we only require commitment in the case of no faults.Lamport tried to get better algorithms for weak Byzantine agreement than for Byzantineagreement, but failed.

Instead he got an impossibility result. Note: In obtaining this result,Lamport did not even need the assumption that the algorithm terminates in a xed numberof rounds, but only that every execution eventually leads to termination for all nonfaultyprocesses. In fact, the impossibility results proved so far in this lecture still work even withthis weakening of the termination requirement. For the present result, we will explicitlyassume the weaker termination requirement.Theorem 4 n 3f +1 processes and conn(G) 2f +1 are needed even for weak Byzantineagreement.We will just show that three processes cannot solve weak Byzantine agreement with onefault the rest of the proof follows as before.Suppose there exist three processes p, q, and r that can solve weak Byzantine agreementwith one fault.

Let P0 be the execution in which all three processes start with 0, no failuresoccur, and therefore all three processes decide 0. Let P1 be the same for 1 instead of 0. Let kbe greater than or equal to the number of rounds in executions P0 and P1. We now create anew system S with at least 4k + 2 nodes by pasting enough copies of the sequence p-q-r intoa ring. Let half the ring start with value 0 and the the other half start with 1 (see Figure6.10).By arguing as we did before, any two consecutive processes must agree therefore, allprocesses in S must agree.

Assume (without loss of generality) that they all decide 1.Now consider a block of at least 2k + 1 consecutive processes that start with 0. For 1round, the middle 2k ; 1 processes in this block will all mimic their namesakes in P0, becausethey do not receive any information from outside the block of 0's. Likewise, for 2 rounds themiddle 2k ; 3 processes will behave as in P0, etc. Finally, the middle process of the groupwill behave as in P0 for k rounds.

Therefore, it will decide 0. This is a contradiction.763211000002S1121111213Figure 6.10: conguration in the proof of Theorem 46.4 Number of Rounds with Stopping FaultsWe now turn to the question of whether Byzantine agreement can be solved in fewer thanf + 1 rounds. Once again the answer is no, even if we require only the weakest validitycondition, namely, that processes must decide v only when all start with v, and no faultsoccur.

In fact, at least f + 1 rounds are required even to simply tolerate f stopping faults.We assume the following model. The number of processes satises n f + 2. Thealgorithm terminates in a xed number of rounds. We also assume, for simplicity, that everyprocess sends to every other process at every round (until it fails). As usual, we assume thata process can fail in the middle of sending at any round, so that it can succeed in sendingany subset of the messages.As for two-generals problem, it is useful to carry out the proof using the notion ofcommunication pattern.Dene a communication pattern to be an indication of which processes send to which otherprocesses in each round. A communication pattern does not tell us the actual informationsent but only \who sent to whom" in a round.

A communication pattern can be depictedgraphically as shown in Figure 6.11. As before, a communication pattern is a subset of setof (i j k) triples, where i and j are distinct processes and k is a round. However, in thestopping-failure case, if a message from some process i fails to reach its destination in roundk, then no messages from i are delivered in any round after k.In the gure, p3 does not send to p2 in round 2. Thus p3 must have stopped and willsend nothing further in round 2 and all future rounds. Essentially, a communication patterndepicts how processes fail in a run.Dene a run as an input assignment and a communication pattern. (This is identical towhat we called adversary in the section on two-generals.) Given any run , we can dene77PROCESSES1234TIMEround 1round 2round 3round 4Figure 6.11: Example of a communication pattern.

Process 3 stops before completing round 1,process 2 stops after completing round 2, processes 1 and 4 are up throughout the execution.an execution exec() generated by . This execution is an alternating sequence of vectors ofstates, one per process, and matrices of messages, one per pair of processes, starting withthe initial states containing the given input values. These states and messages can be lledin using the deterministic message and transition functions. It is possible to infer when aprocess fails by the rst time, if any, when it fails to send a message. After such a failure,it will not perform its state transition function. By convention, we say that a process thatsends all its messages at round k but none at round k + 1, performs the transition of roundk in the execution exec().A process is faulty in a run exactly if it stops sending somewhere in the communicationpattern.

We will only consider runs with at most f faulty processes.The Case of One Failure. First, for intuition, we will consider the special case of f = 1.We show that two rounds are required to handle a single stopping fault. We do this bycontradiction, so assume a 1-round algorithm exists.We construct a chain of executions, each with at most one fault, such that (i) weakvalidity requires that the rst execution must lead to a 0 decision and the last executionmust lead to a 1 decision, and (ii) any two consecutive executions in the chain look thesame to some process that is nonfaulty in both. This implies a contradiction, since if twoexecutions look the same to a nonfaulty process, that process must make the same decisionin both executions, and therefore, by the agreement requirement, both executions must havethe same decision value. Thus every execution in the chain must have the same decision78value, which is impossible since the rst execution must decide 0, and the last must decide1.We start the chain with the execution exec(0) determined from the run 0 having all0 input values and the complete communication pattern, as in Figure 6.12.

This executionmust decide 0.0 H*@HJ;000J@HHH ;J@;HJ @; HHjH*@HHJ;@;@;HJ @;H;@ J H;@ @;J H@;jHRH*H ;@ JH;H@JHH@;HJ@;jHR^JFigure 6.12: A run, 0, which must decide 0.Starting from execution exec(0), form the next execution by removing the message fromp1 to p2. These two executions look the same to all processes except p1 and p2. Sincen f +2 = 3, there is at least one such other process, and it is nonfaulty in both, and hencemust decide the same in both.Next we remove the message from p1 to p3 these two look the same to all processesexcept p1 and p3 .

We continue in this manner removing one message at a time in such a waythat every consecutive pair of executions looks the same to some nonfaulty process.Once we have removed all the messages from p1, we continue by changing p1's input valuefrom 0 to 1. Of course these two executions will look the same to every process except p1since p1 sends no messages. Now we can add the messages back in one by one, and againevery consecutive pair of executions will look the same to some nonfaulty process. Thisall yields exec(1), where 1 has 1 as input value for p1, 0 for all the others, and completecommunication.Next, we repeat this construction for p2, removing p2's messages one-by-one, changingp2's input value from 0 to 1, and then adding p2's messages back in.

This yields 2. Repeatingthis construction for p3,: : : ,pn, we end the chain with the execution exec(n), where all startwith 1 and there is complete communication. This execution must decide 1. Thus we haveproduced a chain as claimed, and this is a contradiction.The Case of Two Failures. Before moving to the general case, we will do one morepreliminary case. We will now show that two rounds are not sucient to handle two stopping79failures. Again, we proceed by contradiction. We form a chain as we did for the case of onefault and one round.

We start with the execution determined by all 0's as input and thecomplete (2-round) communication pattern this execution must decide 0.To form the chain we want again to work toward killing p1 at the beginning. When wewere only dealing with one round we could kill messages from p1 one-by-one. Now, if wedelete a rst-round message from p1 to q in one step of the chain, then it is no longer thecase that the two executions must look the same to some nonfaulty process. This is becausein the second round q could inform all other processes as to whether or not it received amessage from p1 in the rst round, so that at the end of the second round the two executionscan dier for all non-faulty processes.We solve this problem by using several steps to delete the rst-round message from p1to q, and by letting q be faulty too (we are allowed two faults).

We start with an executionin which p1 sends to q in the rst round and q sends to every process in the second round.Now we let q be faulty and remove second-round messages from q, one-by-one, until we havean execution in which p1 sends to q in the rst round and q sends no messages in the secondround.