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

Consider the processes p-q-r-p0 in S with the given inputs. To q and r, it appears as ifthey are running in the three process system P , in which p is faulty (i.e., \pretending" it'srunning in a 6-processor system). This is an allowable behavior for Byzantine Agreement onthree processes, and the correctness conditions for BA imply that q and r must eventually68p SSS XX XXSSXXzSSqrpSSS*SSSSqrpq;0;;;;;@ 0@@@@ 0@rr0@@@@@;1@;;;1 ;;1q0p0Figure 6.1: The system S : arrangement of processes in the proof of Lemma 1agree on 0 in the three-process system. Since the six-process system S appears identical toq and r, both will eventually decide on 0 in S as well.Next consider the processes r-p0 -q0-r0. By similar reasoning, p0 and q0 will eventually agreeon 1 in S .Finally consider the processes q-r-p0-q0. To r and p0, it appears as if they are in a threeprocess system with q faulty.

Then r and p0 must eventually agree in P (although there isno requirement on what value they agree upon), and so they agree in S . However this isimpossible since we just saw that r must decide 0 and p0 must decide 1, and we arrived tothe desired contradiction.We now use Lemma 1 to show that Byzantine agreement requires n 3f + 1 processesto tolerate f Byzantine faults LamportPS82]. We will do this by showing how an n 3fprocess solution that can tolerate f Byzantine failures implies the existence of a 3 processsolution which can tolerate a single Byzantine failure. This contradicts the above lemma.Theorem 2 There is no solution to the Byzantine agreement problem on n processes in thepresence of f Byzantine failures, when 1 < n 3f .Proof: Assume there is a solution for Byzantine agreement with 3 n 3f . (For n = 2,there can be no agreement: if one process starts with 0 and the other with 1, then each mustallow for the possibility that the other is lying and decide on its own value.

But if neitheris lying, they this violates the agreement property.) Construct a three-process system witheach new process simulating approximately one-third of the original processes. Specically,partition the original processes into three nonempty subsets, P1 , P2, and P3, each of sizeat most f . Let the three new processes be p1, p2, and p3, and let each pi simulate the69original processes in Pi as follows. Each process pi keeps track of the states of all the originalprocesses in Pi , assigns its own initial value to every member of Pi, and simulates the stepsof all the processes in Pi as well as the messages between the processes in Pi. Messages fromprocesses in Pi to processes in another subset are sent from pi to the process simulating thatsubset.

If any simulated process in Pi decides on a value v then pi can decide on the value v.(If there is more than one such value, then pi will choose a particular one, chosen accordingto some default.)To see that this is a correct 3-process solution we reason as follows. At most one of p1, p2,p3 is allowed to be faulty, and each simulates at most f original processes, so the simulationcontains no more than f simulated faults.

(Designate the faulty processes in the simulatedsystem to be exactly those that are simulated by a nonfaulty actual process, regardless ofwhether they actually exhibit a fault.) This is as required by the simulated solution. Then-process simulated solution then guarantees that the simulated processes satisfy agreement,validity, and termination.Let us argue briey that the validity, agreement, and termination of the n-process simulation carry over to the 3-process system. Termination is easy.

For validity, if all nonfaultyactual processes begin with a value v, then all the nonfaulty simulated processes begin withv. Validity for the simulated system implies that the only simulated decision value for asimulated non-faulty process must be v, so the only actual decision value for an actual nonfaulty process is v. For agreement, suppose pi and pj are nonfaulty actual processes. Theythey simulate only nonfaulty processes. Agreement for the simulated system implies that allof these simulated processes agree, so pi and pj also agree.We conclude that given a system that tolerates f n=3 faults, we can construct aprotocol for 3 processes that tolerates one faulty process, contradicting Lemma 1.Let us recap what assumptions have we used for this proof.Locality: A process's actions depend only on messages from its input channels and its initialvalue.Faultiness: A faulty process is allowed to exhibit any combination of behaviors on itsoutgoing channels.

(We could strengthen this assumption, and insist that the behaviorof each channel can arise in some system in which the process is acting correctly.)The locality assumption basically states that communication only takes place over theedges of the graph, and thus it is only these inputs and a process' initial value that can aectits behavior. Note that the nodes are allowed to have information about the network in whichthey are supposed to run (e.g., the three-process network above) built into them, but this70information is not changed \magically" if processes are assembled into an unexpected system(e.g., the six-process network above).The strengthened version of the fault assumption expresses a masquerading capabilityof faulty processes.

We cannot determine if a particular edge leads to a correct process, orto a faulty process simulating the behavior of a correct process over the edge. The faultassumption gives faulty processes the ability to simulate the behaviors of dierent correctprocesses over dierent edges.6.2 Byzantine Agreement in General GraphsWe have shown that Byzantine agreement can be solved with n processes and f faults,where n 3f + 1.

In proving this result, we assumed that any process could send a messagedirectly to any other process. We now consider the problem of Byzantine agreement ingeneral communication graphs Dolev82].Consider a communication graph, G, where the nodes represent processes and an edgeexists between two processes if they can communicate. It is easy to see that if G is a tree, wecannot accomplish Byzantine agreement with even one faulty process.

Any faulty processthat is not a leaf would essentially cut o one section of G from another. The nonfaultyprocesses in dierent components would not be able to communicate reliably, much lessreach agreement. Similarly, if removing f nodes can disconnect the graph, it should also beimpossible to reach agreement with f faulty processes. We formalize this intuition using thefollowing standard graph-theoretic concept.Denition 1 The connectivity of a graph G, conn(G), is the minimum number of nodeswhose removal results in a disconnected graph or a trivial 1-node graph. We say a graph Gis k -connected if conn(G) k .For example, a tree has connectivity 1, and a complete graph with n nodes has connectivity n ; 1. Figure 6.2 shows a graph with connectivity 2.

If q and s are removed, then weare left with two disconnected pieces, p and r.We remark that Menger's Theorem states that a graph is k-connected if and only if everypair of points is connected by at least k node-disjoint paths. We shall use this alternativecharacterization of the connectivity in the sequel.In the following theorem we relate the connectivity of a graph to the possibility of executing a Byzantine agreement protocol over it.

The proof uses methods similar to thoseused in our lower bound proof for the number of faulty processes.Theorem 3 Byzantine agreement can be solved on a graph G with n nodes and f faults ifand only if71ptq tHHHHHHHHHHHHt sHHHHtrFigure 6.2: A graph G with conn(G) = 2.1. n 3f + 1, and2. conn(G) 2f + 1.Proof: We already know that n 3f + 1 processes are required for a fully connectedgraph.

It is easy to see that for an arbitrary communication graph, we still need n 3f + 1(since removing communication links does not \help" the protocols).We now show the if direction, namely, that Byzantine agreement is possible if n 3f +1and conn(G) 2f + 1. Since we are assuming G is 2f + 1-connected, Menger's Theoremimplies that there are at least 2f + 1 node-disjoint paths between any two nodes. We cansimulate a direct connection between these nodes by sending the message along each of the2f + 1 paths. Since only f processes are faulty, we are guaranteed that the value received inthe majority of these messages is correct.

Therefore, simulation of a fully connected graphcan be accomplished, simulating each round of the protocol for a fully-connected graph by atmost n rounds of in G. We have already seen an algorithm that solve Byzantine agreementin this situation.We now prove the only if direction of the theorem. The argument that Byzantine agreement is not possible if conn(G) 2f is a bit more intricate. We will only argue the case forf = 1, for simplicity.Assume there exists a graph, G, with conn(G) 2 in which consensus can be solvedin the presence of one fault, using protocol P . Then there are two nodes in G that eitherdisconnect the graph or reduce it to one node.

But this latter case means that there are onlythree nodes in the graph, and we already know that Byzantine agreement cannot be solvedin a 3-node graph in the presence of 1 fault. So assume they disconnect the graph.The picture is then as in Figure 6.2, where p and r are replaced by arbitrary connectedgraphs (and there may be several edges from each of q and s to each of the two disconnectedgroups). Again for simplicity, however, we just consider p and r to be single nodes. Weconstruct a system S by \rewiring" two copies of P , as shown in Figure 6.3.

Each processin S behaves as if it was the same-named process in P , for the graph in Figure 6.2.72p0st1t@@@@@q0 @tr0@@t@@@@@ts0rt 1@@@t q1tp1Figure 6.3: System S , made by \rewiring" two copies of P .Now assume we start up system S with inputs corresponding to the subscripts. Considerthe behavior of the processes p0, q0 and r0 of S outlined in Figure 6.4. As before, it appearsto all three that they are in P with input 0, as in Figure 6.5, in an execution in which s isa faulty process. By the locality assumption, the outlined processes will behave in the sameway in these two cases. By the validity property for P , these processes must all decide 0 inP , and hence in S .p0ttq0 @st1t r1@@@@@@@@t q1@@@@@@@ttr0s0tp1Figure 6.4: A set of processes in S .Now consider Figure 6.6 and the corresponding 4-node situation of Figure 6.7.

By thesame argument, all the outlined processes will decide 1 in S .Finally, consider Figure 6.8 and its corresponding 4-node situation of Figure 6.9. Since73pt0HHHtq0 HHHHHHHHHHHHt sHtr0Figure 6.5: A conguration of P (with s faulty) that the outlined processes cannot distinguishfrom Figure 6.4.p0st1t@tq0 @@@@@r0trt 1@@@@@@@t q1@@@tts0p1Figure 6.6: Another set of processes in S .pt1tq1 HHHHHHHHHHHHHHHt sHtr1Figure 6.7: A conguration (with s faulty) that the outlined processes cannot distinguish fromFigure 6.6.74only q is faulty, the agreement condition requires that the outlined processes decide on thesame value in P , and hence in S .p0st1t r1@@@@@@@@t q1tq0 t@@@@@@@@ttr0s0tp1Figure 6.8: Yet another set of processes in S .pt1tqHHHHHHHHHHHHtHHHHt s0r0Figure 6.9: The nonfaulty processes must agree, giving us a contradiction.However, we have already shown that process p1 must decide 1 and process r0 mustdecide 0.