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

In the rst round, processes j and k report their values truthfully, and processi tells both others that its value is 0. Consider the view of process j . In the second round,process k tells j that i said 0 and i tells j that k said 0. In this situation, the problemconstraints require that j and k decide 1.Scenario 3: Now suppose that processes i and j are nonfaulty, and start with 0 and 1,respectively. Process k is faulty, but sends the same messages to i that it does in Scenario 1and sends the same messages to j that it is in Scenario 2. In this case, i will send the samemessages to j as it does in Scenario 2, and j will send the same messages to i as it does inScenario 1.

Then i and j must follow the same behavior they exhibited in Scenarios 1 and2, namely, decide 0 and 1, respectively, thereby violating agreement!Note that i can tell that someone is faulty in Scenario 3, since k tells i 0, and j tells i thatk said 1.

But process i doesn't know which of j and k is faulty. We remark that althoughthe protocol could have more rounds, the same kind of argument will carry over. We shallsee later a rigorous proof for the necessity of n > 3f .An Algorithm. We shall now describe an algorithm, assuming n > 3f processes. Recallthe \full information protocol" described in last lecture for stopping faults. The basic ideain the Byzantine case is based on the same tree and propagation strategy as for the stoppingfaults case, but now we shall use a dierent decision rule. It is no longer the case that wewant to accept any value for insertion into the set of \good" values, just because it appearssomewhere in the tree. Now we must beware of liars! We use the following easy fact.Lemma 1 If i, j and k are all nonfaulty, then value i(p) = value j (p) for every label p endingin k .60Proof: Follows from the simple fact that since k is nonfaulty, it sends the same thing toeveryone.Now we can specify a decision rule.If a value is missing at a node, it is set to some pre-specied default.

To determinethe decision for a given tree, we work from the leaves up, computing a new valuenewvalue for each node as follows. For the leaves, newvalue i(p) := value i (p). Foreach node, newvalue is dened to be the majority value of the newvalue 's of thechildren. If no majority value exists, we set newvalue := default . The decision isnewvalue i (root ).We now start proving the correctness of the algorithm.

First we prove a general lemma.Lemma 2 Suppose that p is a label ending with the index of a nonfaulty process. Then thereis a value v such that value i (p) = newvalue i(p) = v for all nonfaulty processes i.Proof: By induction on the tree labels, working from the leaves on up.Base case: Suppose p is a leaf. Then, by Lemma 1, all nonfaulty processes i have thesame value i(p) which is the desired value v, by the denition of newvalue for leaves.Inductive step: Suppose jpj = k , 0 k f . Then Lemma 1 implies that all nonfaultyprocesses i have the same value value i(p) call this value v. Therefore, all the nonfaultyprocesses l send the same value v for pl to all processes.

So for all nonfaulty i and l, wehave value i(pl) = v. By the inductive hypothesis, we have that newvalue i(pl) = v for allnonfaulty processes i and l, for some value v.We now claim that a majority of the child labels of p end in nonfaulty process indices.This is true because the number of children is n ; k n ; f > 2f , and since at most f maybe faulty, we have that there always is a \honest" majority. (Note this is where we use thebound on the number of processes.)The induction is complete once we observe that since for any nonfaulty i, v = newvalue i(pl)for a majority of the children pl, newvalue i(p) = v by the algorithm.We now argue validity.Corollary 3 Suppose all nonfaulty processes begin with the same value v. Then all nonfaultyprocesses decide v.Proof: If all nonfaulty processes begin with v, then all nonfaulty processes send v at therst round, and therefore value i(j ) = v for all nonfaulty processes i j .

Lemma 2 impliesthat newvalue i (j ) = v for all nonfaulty i and j , and therefore, newvalue i(root ) = v for allnonfaulty i.Before we show agreement, we need a couple of additional denitions.61Denition 1 Consider an execution of the algorithm. A tree node p is said to be commonin the given execution if, at the end of the execution, all the nonfaulty processes have thesame newvalue (p).Denition 2 Consider a rooted tree T . A subset of the tree-nodes C is a path covering ofT if every path from a leaf to the root contains at least one node from C .

A path covering iscommon if it consists entirely of common nodes.Lemma 4 There exits a common path covering of the tree.Proof: Consider any path. Each of the f + 1 nodes on the path ends with a distinct index,and therefore there exists a node on the path, say p, with a label that ends in a nonfaultyindex. Then Lemma 2 implies that p is common.Lemma 5 Let p be a node. If there is a common path covering of the subtree rooted at p,then p is common.Proof: By induction on p, starting at the leaves and working up.Base case: If p is a leaf, there is nothing to prove.Inductive step: Suppose p is at level k .

Assume that there is a common path covering Cof p's subtree. If p itself is in C , then p is common and we are done, so suppose p 2= C .Consider any child pl of p. C induces a common path covering for the subtree rooted atpl.

Hence, by the inductive hypothesis, pl is common. Since pl was an arbitrary child of p,all the children of p are common, which in turn implies that p is common by the denitionof newvalue.We can now conclude that the algorithm satises the validity requirement.Corollary 6 The root is common.Proof: By Lemmas 4 and 5.Authentication. The original paper of Lamport, Pease and Shostak, and a later paperof Dolev and Strong, present algorithms that work in the presence of Byzantine failures,but where the nodes have the extra power of authentication based on digital signatures.Informally, this means that no one can claim that another process said something unless infact it did.

There is no nice formal characterization given for this model. The interestingfact is that the algorithm is much like the stopping fault algorithm, rather than the fullByzantine algorithm above. In particular, it works for any number of processes, even whenn < 3f .625.2 Reducing the Communication CostA major drawback of the algorithms presented above is that they require an excessive amountof communication | specically, the number of messages communicated in the tree algorithms is exponential in f . (Here, we are counting the separate values being sent as separatemessages, though in terms of the formal model, many would be packaged into a single message.

The bound would be better expressed in terms of the number of bits of communication.)In this section we discuss some methods to cut down this cost.5.2.1 Stopping FaultsWe start by reducing the number of messages communicated in the stopping faults algorithmto polynomial in f . Let us examine the algorithm described in the previous lecture moreclosely. In that algorithm, we have everyone broadcasting everything to everyone.

However,in the end, each process only looks to see whether the number of distinct values it has receivedis exactly 1. Consider a process which has already relayed 2 distinct values to everyone. Weclaim that this process doesn't need to relay anything else, since every other process alreadyhas received at least two values. Thus, the algorithm boils down to following rule.Use the \regular" algorithm, but each process prunes the messages it relays sothat it sends out only the rst two messages containing distinct values.The complexity analysis of the above algorithm is easy: the number of rounds in is thesame as before (f +1), but the number of messages is only O(n2), since in total, each processsends at most two messages to each other process.What is a bit more involved is proving the correctness of the above algorithm.

In whatfollows we only sketch a proof for the correctness of the optimized algorithm. The maininterest lies in the proof technique we employ below.Let O denote this optimized algorithm, and U the unoptimized version. We prove correctness of O by relating it to U . First we need the following property.Lemma 7 In either algorithm O or algorithm U , after any number k of rounds, for anyprocess index i and for any value v, the following is true. If v appears in i's tree, then itappears in the tree at some node for which the index i is not in the label.Lemma 7 is true because there are only stopping failures, so i can only relay a value, andothers claim i relayed it, if i in fact originally had it.Dene values O(i k), 0 k f +1, to be the set of values that appear in levels f0 : : : kgof process i's tree in O. We dene values U (i k) analogously.

The following lemma is immediate from the specication of algorithm U .63Lemma 8 In algorithm U , suppose that i sends a round k + 1 message to j , and j receivesand processes it. Then values U (i k) values U (j k + 1).The key pruning property of O is captured by the following lemma.Lemma 9 In algorithm O, suppose that i sends a round k + 1 message to j , and j receivesand processes it.1.

If jvalues O (i k)j 1, then values O (i k ) values O (j k + 1).2. If jvalues O (i k)j 2, then jvalues O (j k + 1)j 2.Note that Lemma 7 is required to prove Lemma 9.Now to see that O is correct, imagine running the two algorithms side-by-side : O, thenew optimized algorithm, and U , the original unoptimized version, with the same initialvalues, and with failures occurring at the same processes at exactly the same times. (If aprocess fails at the middle sending in one algorithm, it should fail at the same point in theother algorithm.) We state \invariants" relating the states of the two algorithms.Lemma 10 After any number of rounds k, 0 k f + 1: values O (i k) values U (i k).Lemma 11 After any number of rounds k, 0 k f + 1:1. If jvalues U (i k)j 1 then values O (i k) = values B (i k).2.