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

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

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

Then run p2 until it rst covers v2. Note that we are not doneyet, because p2 could have written v1 since last leaving R. But now, we can resume p1 untilpoint t3. The rst thing it does is write v1, thereby overwriting anything p2 wrote. Then p1and p2 cover variables v1 and v2, respectively. Moreover, by stopping p1 and p2 back in theirmost recent remainder regions, the shared memory and state of p3 would still be the same.This completes the construction of the execution in which p1 and p2 cover the two shared132variables, in a state that is indistinguishable for p3 from the state in which both are in R.By the argument above, we conclude that in this case, mutual exclusion can be violated.11.3.3 The General CaseThe proof for the general case extends the examples above with an inductive argument.

Wecall a state a global remainder state if all processes are in R in that state. We call a statek-reachable from another if it is reachable using steps of processes p1 : : : pk only.We start with two preliminary lemmas.Lemma 11 Suppose A solves mutual exclusion with deadlock-freedom for n 2 processes,using only read-write variables.

Let s and s0 be reachable states of A, that are indistinguishable to pi , and suppose that s0 is a global remainder state. Then pi can go, on its own, froms to its critical region.Proof: Process pi can do so in s0, by deadlock-freedom. Since s looks like s0 to pi, it canbehave in the same way from s.Lemma 12 Suppose A solves mutual exclusion with deadlock-freedom for n 2 processes,using only read-write variables.

Let s be a reachable state of A. Suppose that i goes from Rto C on its own starting from s. Then along the way, i must write to some variable that isnot covered in s.Proof: If not, then after pi enters, can resume the others, who overwrite and hide it.Using the above easy properties, we shall prove the following main lemma.Lemma 13 Let A be an n process algorithm solving mutual exclusion with deadlock-freedom,using only read-write variables.

Let s0 be any reachable global remainder state. Suppose1 k n. Then there are two states s and s0, each k-reachable from s0, such that thefollowing properties hold.1. k distinct variables are covered by p1 : : : pk in s.2. s0 is a global remainder state.3. s looks like s0 to pk+1 : : : pn .Notice that applying this lemma for k = n yields the theorem.Proof: By induction on k.Base case: For k = 1, we have the rst example above.

To get s, just run p1 till it coversa variable. In this case, we dene s0 = s0.Inductive step: suppose the lemma holds for k we prove it holds for k + 1 n. Startingfrom s0, by induction, we run p1 : : : pk until they reach a point where they cover k distinct133variables, yet the state looks to pk+1 : : : pn like some global remainder state that is kreachable from s0. Then, we let p1 : : : pk write in turn, overwriting the k variables, andthen let them progress to C , E , R, calling the resulting state s1.

We apply the inductivehypothesis again to reach another covering state s2 that looks like a global remainder staten1k-reachable from s . We repeat this procedure k + 1 times. Now, by the PigeonholePrinciple, among the nk + 1 covering states that have been obtained, there must be twothat cover the same set of variables. Let t1 be the rst of these points in the execution, t2the second.

Let s1 and s01 be the covering and global remainder states corresponding to t1,and likewise s2 and s02 for t2.Consider running pk+1 alone from t1. Since the state at t1 looks to pk+1 like a reachableglobal remainder state, Lemma 11 implies that pk+1 will eventually enter C . Along the way,by Lemma 12, it must write to some variable not in V .Now we construct the needed execution to prove the lemma as follows (see Figure 11.5).First, run p1 : : : pk until t1 then let pk+1 take steps until it rst covers a variable not in V .Next, let p1 : : : pk resume and go to t2.Critical RegionRemainder Region1,...,kt1k+11,...,kt’t2Figure 11.5: construction for the general case.

In t1, processes p1 : : : p cover k variables of V . Int , pk+10kcovers some variable not in V . In t2 , V and that variable are covered.Call the resulting state s this is the s that is required in the statement of the lemma.(This state s is the same as s2, with the state of pk+1 changed to what it is when it stops.)Let s0 = s02.We now show that the required properties hold. First, note that the entire construction(including the uses of the inductive hypothesis), only involves running p1 : : : pk+1 , so boths and s0 are k + 1-reachable from s0.

Also, directly from the construction, we have k + 1variables covered in s: the k variables in V , and a new one covered by pk+1 . By inductivehypothesis, s02 = s0 is a global remainder state.It remains only to show that s and s0 look alike to pk+2 : : : pn . But this follows from thefacts that s2 and s02 look alike to pk+1 : : : pn , and that s2 and s look alike to all processes134except pk+1 .1356.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchOctober 22, 1992Lecture 1212.1 Consensus Using Read-Write Shared MemoryIn this section, we focus on the consensus problem in the shared memory setting.

We shallwork from papers by Herlihy Loui, Abu-Amara and Fischer, Lynch, Paterson. We rstdene the problem in this context. The architecture is the same architecture we consideredin the previous lectures, namely, read-write shared variables (allowing multi-reader, multiwriter variables). Here, we assume that the external interface consists of input action init i(v),where v is the input value, and output action decide i(v), where v is the decision value. Justto keep consistent with the invocation-response style we are using for mutual exclusion andatomic objects, we assume that the initial values arrive from the outside in input actions.interfacelineprocesssharedmemorycellFigure 12.1: shared memory systemWe require the following properties from any execution, fair or not:Agreement: All decision values are identical.136Validity: If all processes start with the same value v, then v is the only possible decision.In addition, we need some kind of termination condition.

The simplest would be the following.Termination: If init events occur at all nodes and the execution is fair, then all processeseventually decide.This condition (which applies only when there are no faults), has simple solutions, eventhough there is asynchrony. So it is only interesting to consider the faulty case. In thefollowing requirement, we give the formulation of the requirement for stopping faults.Termination: Suppose init events occur at all processes, and let i be any process.

If i doesnot fail (i.e., the execution is fair to i) then eventually a decide i event occurs.We remark that this condition is similar to wait-freedom.12.1.1 Impossibility for Arbitrary Stopping FaultsOur rst result in this section is the following.Theorem 1 There is no algorithm for consensus that tolerates stopping faults.Proof: Assume that A is a solution. Suppose for simplicity that the values in A are chosenfrom f0 1g. Without loss of generality, we can assume that the state-transition relation ofA is \process-deterministic", i.e., from any global state, if a process i is enabled to take anon-input step, then there is a unique new global state that can result from its doing so.Also, for any global state and any input, there is a unique resulting global state.

This doesnot restrict the generality since we could just prune out some of the transitions the problemstill has to be solved in the pruned algorithm.We can further restrict attention to input-rst executions of A, in which inputs arriveeverywhere before anything else happens, in order of process index. That is, they havea prex of the form init 1(v1) init 2(v2) : : : init n (vn). This is just a subset of the allowedexecutions.

Now consider any nite input-rst execution of A. We say that is 0-valentif the only value v that ever appears in a decide (v) event in or any continuation of is 0analogously, we say that is 1-valent if the only such value v is 1. We say that is univalentif it is either 0-valent or 1-valent, and bivalent if both values appear in some extensions.Note that this classication is exhaustive, because any such can be extended to a fair(i.e., failure-free) execution of A, in which everyone is required to eventually decide.Dene an initial execution of A to be an input-rst execution of length exactly n. Thatis, it consists of exactly n init i actions, one for each i (in order of process index).137Lemma 2 There exists an initial execution of A that is bivalent.Proof: If not, then all initial executions are univalent. Note that the one in which all startwith 0 is 0-valent, and analogously for 1.

Now consider changing one 0 at a time to a 1.This creates a chain of initial executions, where any two consecutive initial executions in thischain only dier in one process' input. Since every initial execution in the chain is univalent,by assumption, there must be two consecutive initial executions, and 0, such that is0-valent and 0 is 1-valent.

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

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