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

If jvalues U (i k)j 2 then jvalues O (i k )j 2.Proof: By induction. Base case is immediate. Assume now that the lemma holds for k.We show it holds for k + 1.1. Suppose jvalues U (i k + 1)j 1. It follows that jvalues U (i k)j 1, so by inductivehypothesis, we have values O (i k) = values U (i k). By Lemma 10, it suces to showthat values U (i k + 1) values O (i k + 1).Let v 2 values U (i k +1). If v 2 values U (i k) then v 2 values O (i k) values O (i k +1).So now assume that v 2= values U (i k + 1). Suppose v arrives at i in a round k + 1 ina message from some process j , where v 2 values U (j k).

Since jvalues U (i k + 1)j 1,Lemma 8 implies that jvalues U (j k)j 1. By inductive hypothesis, values O (j k) =values U (j k), and so jvalues O (j k )j 1. By Lemma 9, values O (j k ) values O (i k +1),and hence v 2 values O (i k + 1), as needed.2. Suppose jvalues U (i k + 1)j 2. If jvalues U (i k)j 2 then by inductive hypothesis, wehave jvalues O(i k)j 2, which implies the result. So assume that jvalues U (i k)j 1.By the inductive hypothesis, we have values O (i k) = values U (i k). We consider twosubcases.64(a) For all j from which i receives a round k + 1 message, jvalues B (j k) 1j.In this case, for all such j , we have by inductive hypothesis that values A (j k) =values B (j k). Lemma 9 then implies that for all such j , values U (j k ) values O (i k+1). It follows that values O(i k +1) = values U (i k +1), which is sucient to provethe inductive step.(b) There exists j from which i receives a round k+1 message such that jvalues U (j k)j 2.By the inductive hypothesis, jvalues O (j k)j 2.

By Lemma 9, jvalues A (i k +1)j 2, as needed.The truth of Lemma 11 for k = f + 1, and the fact that Wi = Wj for nonfaulty i and jin U , together imply that i and j decide in the same way in algorithm O: this follows fromconsidering the two cases in which Wi and Wj in U are singletons or have more than onevalue (Wi 6= , since the root always gets a value).Note: The proof technique of running two algorithms side by side and showing that theyhave corresponding executions is very important. In particular, in cases where one algorithmis an optimization of another, it is often much easier to show the correspondence than it is toshow directly that the optimized algorithm is correct. This is a special case of the simulationproof method (cf.

Model Section in the bibliographical list).5.2.2 The Byzantine CaseIn the Byzantine model, it does not seem so easy to obtain an optimized, pruned algorithmwith a polynomial number of messages. We only summarize results in this section.Polynomial communication and 2f + k rounds (for constant k), assuming n 3f + 1processes, was achieved by a fairly complex algorithm by Dolev, Fischer, Fowler, Lynch, andStrong DolevFFLS82].Essentially this algorithm was expressed in a more structured fashion by Srikanth andToueg SrikanthT87]. Their structure involved substituting an authentication protocol forthe assumed signature scheme in an ecient authenticated BA algorithm (used one by Dolevand Strong).

Using this authentication protocol requires twice the number of rounds as doesthe Dolev-Strong protocol, and also needs 3f + 1 processes. The basic idea is that whenevera message was sent in the Dolev-Strong algorithm, Srikanth and Toueg run a protocol tosend and accept the message.An improvement on the 2f rounds required by the above algorithms was achieved by CoanCoan86], who presented a family of algorithms requiring f +f rounds, where 0 < 1.

The65message complexity is polynomial, but as approaches zero, the degree of the polynomialincreases. An important consequence of this result is that no lower bound larger thanf + 1 rounds can be proved for polynomial algorithms, although no xed degree polynomialalgorithm is actually given for f + 1 rounds. A paper by Bar Noy, Dolev, Dwork, and StrongBarNoyDDS87] presents similar ideas in a dierent way. We remark that they introducedthe tree idea used above to present the consensus algorithms.Moses and Waarts achieve f + 1 rounds with polynomial communication MosesW88].The protocol looks pretty complicated, with many involved strategies for pruning the tree.Also, it does not work for 3f +1 processors as does the exponential communication protocol,but rather forBerman and Garay use a dierent approach to solve the same problem as MW.

Theyachieve 4f + 1 processors and r + 1 rounds. Their algorithm is still fairly complicated.5.2.3 The Turpin-Coan AlgorithmIt is hard to cut down the amount of communication for general Byzantine agreement. Weclose this topic with an interesting trick that helps somewhat, though it does not reducethe communication from exponential to polynomial. The problem addressed here is how toreduce BA for a multivalued domain to binary-valued BA. In other words, the algorithm wepresent uses binary BA as a subroutine. If the domain is large, the savings can be substantial.In the Turpin-Coan algorithm we assume that n 3f + 1, and that default value isknown initially by all non-faulty processes.

For each process, a local variable x is initializedto the input value for that process.Below, we describe the Turpin-Coan algorithm. This time, the style is changed a littlebit. Namely, the code for each round is written explicitly. Implicitly, we assume that thecode will be executed for rounds 1 2 : : : in sequence. Of course, in the underlying statemachine model, this convention is expanded into manipulation of an explicit round variable,which gets read to determine which code to perform, and gets incremented at every round.Round 1:1. Broadcast x to all other processes.2. In the set of messages received, if there are n ; f for a particular value, v, thenx := v, otherwise x nil .Round 2:1.

Broadcast x to all other processes.662. Let vmax be the value, other than nil, that occurs most often among those valuesreceived, with ties broken in some consistent way. Let num be the number ofoccurrences of vmax .3. if num n ; f then vote = 1 else vote = 0.After round 2, run the binary Byzantine agreement subroutine using vote as the inputvalue. If the bit decided upon is 1, then decide vmax , otherwise decide the default value.Claim 12 At most one value v is sent in round 2 messages by correct processes.Proof: Any process p sending a value v in round 2 must have received at least n ; f round1 messages containing v.

Since there are at most f faulty processes, this means that all otherprocesses received at least n ; 2f copies of v. Since the total number of messages receivedis n, no process could have received n ; f messages containing a value v0 6= v in round 1.Therefore, the claim holds.Theorem 13 The Turpin-Coan algorithm solves multivalued Byzantine agreement whengiven a Boolean Byzantine agreement algorithm as a subroutine.Proof: It is easy to see that this algorithm terminates.To show validity, we must prove that if all nonfaulty processes start with a value, w,then all nonfaulty processes must decide w.

After the rst round, all nonfaulty processeswill have set x w because at least n ; f processes broadcast it reliably. Therefore, inthe second round, each nonfaulty process will have vmax = w and num n ; f , and willtherefore obtain vote = 1. The binary agreement subroutine is therefore required to choose1, and each nonfaulty process will choose w.In showing agreement, we consider two cases. If the subroutine decides on vote = 0, thenthe default value is chosen by all nonfaulty processes, so agreement holds. If the subroutinedecides on vote = 1, then we must argue that the local variable vmax is the same for eachnonfaulty process.

Note that for the subroutine to agree on vote = 1, then some nonfaultyprocess p must have started with vote = 1. Therefore, process p must have received atleast n ; f round 2 messages containing some particular value v. Since there are at most ffaulty processes, each other process must have received at least n ; 2f round two messageswith non-nil values from nonfaulty processes.

By Claim 12, all of the non-nil messages fromnonfaulty processes must have the same value, namely v. Therefore, v must be the valueoccurring most often, since there are at most f faulty processes and n ; 2f > f .The proof method uses a bound on the number of faulty processes to obtain claims aboutsimilarity between the views of dierent processes in a fault-prone system. This is a usefultechnique.676.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchSeptember 29, 1992Lecture 6We have seen algorithms for distributed agreement, even in the case of Byzantine faults.The algorithm we saw used n 3f + 1 processes and f + 1 synchronous rounds of communication. In this lecture we will consider whether these bounds are necessary.6.1 Number of Processes for Byzantine AgreementIt turns out that it is impossible to beat the 3f +1 upper bound on the number of processes,i.e., if n 3f , then there is no protocol that ensures agreement.

The proof is neat. We rstprove that three processes cannot tolerate one fault, as suggested in an earlier example (lastlecture). We then show why is it impossible to tolerate f n=3 faults for any n.The rst proof of this appeared in PeaseSL80] the proof given here follows that inFischerLM86].Lemma 1 Three processes cannot solve Byzantine agreement in the presence of one fault.Proof: By contradiction. Assume there is a protocol P consisting of three processes, p,q and r, such that P with arbitrary inputs will satisfy the Byzantine agreement conditionseven if one process malfunctions. We shall construct a new system S from (copies of) thesame processes, and show that S must exhibit contradictory behavior.

It follows that Pcannot exist.Take two copies of each process in P , and arrange them into a 6-process system S asshown in Figure 6.1.When congured in this way, the system appears to every process as if it is congured inthe original three-process system P . Notice that the processes are not required to produceany specic output in S however, S with any particular input assignment does exhibit somewell-dened behavior. We shall see that no such well-dened behavior is possible.Suppose that the processes in S are started with the input values indicated in Figure6.1.