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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 72)

Eachprocess (node) i is an I/O automaton. There are inputs and outputs init i(v) and decide i(v),348respectively, where i is a node and v is a value. There are also outputs broadcast i(v) andinputs receive j i(v), where i and j are nodes and v is a value. The eect of a broadcast i(v)action is to put (atomically) a v message in the channels leading to all the nodes (other thani) in the system. With the broadcast action we actually don't need individual send actions.We assume without loss of generality that each process has only one fairness class (i.e.,the processes are sequential ), and that the processes are deterministic, in the sense that (1)in each process state, there is at most one enabled locally controlled action, and (2) for eachstate s and action , there is at most one new state s0 such that (s s0) is a transition of theprotocol.

In fact, we can assume furthermore (without loss of generality) that in each statethere is exactly one enabled locally controlled action (since we can always add in dummysteps).Correctness Requirement. For the consensus problem we require that in any executionsuch that exactly one init i occurs for each node i, we have the following conditions satised.Agreement: There are no two dierent decision values.Validity: If all the initial values are the same value v, then v is the only possible decisionvalue.In addition, we need some termination conditions. First, we require that if there isexactly one init i for each i and if the entire system (processes and queues) executes fairly,then all processes should eventually decide. This condition is easy to satisfy (e.g., justexchange values and take majority). But we require more.

Dene 1-fair executions to bethose in which all but at most 1 process execute fairly, and all channels execute fairly.We assume that a process that fails still does its input steps, but it can stop performinglocally-controlled actions even if such actions remain enabled. We require that in all 1-fairexecutions, all processes that don't stop eventually decide.It seems as though it ought to be possible to solve the problem for 1-fair executionsalso, especially in view of the powerful broadcast primitive (you should try to design analgorithm!). Our main result in this section, however, is the following theorem.Theorem 1 There is no 1-resilient consensus protocol.Henceforth, we shall restrict our attention to the binary problem, where the input valuesare only 0 and 1 | this is sucient to prove impossibility.Terminology. Dene A to be a 0-resilient consensus protocol (0-RCP) provided that itsatises agreement, validity, and termination in all its fair executions.

Dene A to be a3491-resilient consensus protocol (1-RCP) provided it is a 0-resilient consensus protocol and if,in addition, all non-stopped processes eventually decide in 1-fair executions.We call a nite execution 0-valent if 0 is the only decision value in all extensions of. (Note: the decision can occur anywhere in the extension, including the initial segment.) Similarly, we dene 1-valent nite executions.

We say that is univalent if it is either0-valent or 1-valent, and we say that is bivalent if it is not univalent (i.e., is bivalentif there is one extension of in which someone decides 0, and another extension in whichsomeone decides 1).These \valency" concepts capture the idea that a decision may be determined, althoughthe actual decision action might not yet have occurred. As in the shared memory case,we will restrict attention in the proof to input-rst executions, i.e., executions in which allinputs arrive at the beginning, in round robin order of init events, for process 1 2 : : : n.Dene an initial execution to be an input-rst execution of length exactly n that is, aninitial execution just provides the initial values to all the processes.We can now start proving the impossibility result.

We begin with a statement about theinitial executions.Lemma 2 In any 1-RCP there is a bivalent initial execution.Proof: The idea is the same as in the shared memory setting. Assume that the lemma isfalse, i.e., that all initial executions are univalent. By validity, the all-0 input must lead todecision of 0, and all 1's to decision of 1. By assumption, any vector of 0's and 1's leadsto a unique decision.

Hence there exist two input vectors with Hamming distance 1, withcorresponding initial executions such that one is 0-valent, and the other is 1-valent let and be these two respective initial executions. Let i be the index of the unique processin whose initial value they dier.The idea is that the rest of the system can't tell which of the vectors was input if i neverdoes anything. More formally, consider a 1-fair execution 0 that extends initial execution , in which i fails right at the beginning, i.e., it takes no locally-controlled steps. In 0some process j eventually decides 0, by the assumptions that is 0-valent and that theprotocol is 1-RCP.But then we claim that there is another execution 0 that extends , that also leads todecide j (0).

This is because the only dierence between the states at the end of and is in the state of process i now allow the same processes to take the same steps in 0 as in0 , the same messages to get delivered, etc. (see Figure 25.1). The only dierence in how0 and 0 will unfold is in the state changes caused by the receipt of the same message by iin the two executions { those states can be dierent, but since i never performs any locallycontrolled action in either, the rest of the system cannot tell the dierence.01000011011001350αα0α’01α’100Figure 25.1: In both extensions for and the same processes take the same actions, andtherefore cannot be 1-valent.011Hence, process j must decide 0 in 0 too, contradicting the 1-valence of .Examples.

The majority protocol is a 0-RCP it has no bivalent initial execution, sincean initial execution can only lead to a decision of v in case the value v is the initial value ofa majority of the processes.Another example of an 0-RCP is a leader-based protocol, where everyone sends theirvalues to process 1, and 1 decides on the rst value received and informs everyone else aboutthe decision.

This does have bivalent initial executions { anything in which there are twoprocesses other than p having dierent initial values.We now proceed with the denition of a decider (which is dened somewhat dierentlyfrom the way it was dened for the shared memory setting).De nition 1 A decider for an algorithm A consists of an input-rst execution of A anda process index i such that the following conditions hold (see Figure 25.2).1111. is bivalent.2.

There exists a 0-valent extension 0 of such that the sux after consists of stepsof process i only. (These can be input, output or internal steps.)3. There exists a 1-valent extension 1 of such that the sux after consists of stepsof process i only.Note that the exibility in obtaining two dierent executions here arises because of thepossible dierent orders of interleaving between locally controlled steps and message-receipt351ααα01ionlyionly0−valent1−valentFigure 25.2: schematic diagram of a decider ( i).steps on the various channels.

Also, messages could arrive in dierent orders in two dierentexecutions.Let us now state a lemma about the existence of a decider.Lemma 3 Let A be any 0-RCP with a bivalent initial execution. Then there exists a deciderfor A.We shall prove this lemma later. Let us rst complete the impossibility proof, givenLemma 3.Proof: (of Theorem 1). Suppose A is a 1-RCP. Since A is also a 0-RCP, and since ithas a bivalent initial prex, we can obtain, by Lemma 3, a decider ( i).

We now argue acontradiction in a way that is similar to the argument for the initial case.Consider a 1-fair extension of in which i takes no locally-controlled steps (i.e., ifails right after ). Eventually in , some process j must decide suppose without loss ofgenerality that the decision value is 0. Also, we can suppose without loss of generality thatthere are no message deliveries to i in the sux of after (if there are any, then omittingthem still leads to the same decision).Now we claim that the there is another execution 0 that extends , and that also leadsto decide j (0) (see Figure 25.3).This is because the only dierences between the states at the end of and are in (a)the state of process i, (b) the last elements in the channels leaving process i (there can besome extras after ), and (c) the rst elements in the channels entering process i can bedierent (there can be some messages missing after ).

Then we allow the same processesto take the same steps in the sux after as in , the same messages to get delivered, etc.(Nothing that i has done will interfere with this note that we never deliver any of the extra2222111112352ααα0ionly0−valent1αionly2 no isteps1−valentprocess j decides 0α’2 no istepsprocess j decides 0Figure 25.3: Contradiction derived from the existence of a decider .messages). As before, the only dierence in what happens is in the state changes caused bythe receipt of the same message by i in the two executions: those states can be dierent, butsince i never performs any locally controlled action in either, the rest of the system cannottell the dierence.Hence, process j decides 0 by the end of 0 , contradicting the 1-valence of .It remains now to prove Lemma 3.Proof: (of Lemma 3).

Характеристики

Список файлов книги