Distributed Algorithms. Nancy A. Lynch (1993) (811416), страница 71
Текст из файла (страница 71)
Unfortunately, this model,traditionally called central demon model is not adequate for a truly distributed system, whichis based on loosely coordinated asynchronous processes. And as one might suspect, the maxrule does not work in a truly distributed system.So here is a solution.8>< minu2N (v) fP (u) + 1gP (v) > maxu2N (v) fP (u) ; 1g: P (v )if 8u 2 N (v) : jP (u) ; P (v)j 1if 9u 2 N (v) : P (u) ; P (v) > 1otherwise(24.13)In words, the rule is to apply \minimum plus one" when the neighborhood seems to bein a legal conguration, and if the neighborhood seems to be illegal, to apply \maximumminus one".The intuition behind the modication is that if nodes change their pulse numbers to bethe maximum of their neighbors, then \race condition" might evolve, where nodes with highpulses can \run away" from nodes with low pulses.
If the correction action takes the pulsenumber to be one less than the maximum, then the high nodes are \locked", in the sensethat they cannot increment their pulse counters until all their neighborhood have reachedtheir pulse number. This \locking" spreads automatically in all the \infected" area of thenetwork.343We shall now prove that this rule indeed stabilizes in time proportional to the diameterof the network.
For this we shall need a few denitions.De nition 3 Let v be a node in the graph. The potential of v is denoted by (v) and isdened by(v) = maxfP (u) ; P (v ) ; dist (u v )g :u2VIntuitively, (v) is a measure of how much is v not synchronized, or alternatively thesize of the largest skew in the synchronization of v, corrected by the distance. Pictorially,one can think that every node u is a point on a plane where the x-coordinate represents thedistance of u from v, and the y coordinate represents the pulse numbers (see Figure 24.9for an example).
In this representation, v is the only node on the y-axis, and (v) is themaximal vertical distance of any point (i.e., node) above the 45-degree line going through(0 P (v)).pulse numberspulse numberseinlialtab10tenpo6 Φ (c)teepo6d5einllianted5Φ (b)cφ(c)336544φ(b)c212bed1aba001(i)c32(ii)3 distance from c123 distance from b(iii)Figure 24.9: On the left is an example of a graph with pulse assignment (i). Geometricalrepresentations of this conguration are shown in (ii) and (iii). The plane corresponding tonode c is in the middle (ii), and the plane corresponding to node b is on the right (iii).
Ascan be readily seen, (c) = 1, and (b) = 4. Also, (c) = 1, and (b) = 1 (see Denition4).Let us start with some properties of that follow immediately from the denition.Lemma 8 For all nodes v 2 V , (v) 0.Lemma 9 A conguration of the system is legal if and only if for all v 2 V , (v) = 0.We now show the key property of the new rule, namely that the potential of the nodesnever increases under this rule.344Lemma 10 Let P be any pulse assignment, and suppose that node u changes its pulsenumber by applying the rule. Denote the new pulse number of u by P 0 (u), and the potentialof the nodes in the new conguration by 0. Then for all nodes v 2 V , 0 (v ) (v ).Proof: The rst easy case to consider is the potential of u itself.
Since P 0(u) > P (u), wehave0(u) = maxfP (w) ; P 0(u) ; dist (w u)gw 2V maxfP (w) ; P (u) ; dist (w u)gw 2V= (u) :(24.14)(Note, for later reference, that the inequality in (24.14) is strict if (u) > 0.) Now considerv 6= u. The only value that was changed in the setfP (w) ; P (v ) ; dist (w v ) j w 2 V gis P (u) ; P (v) ; dist(u v). There are two cases to examine.
If u changed its pulse by applyingthe \min plus one" part of the rule, then there must be a node w which is a neighbor of u,and is closer to v, i.e., dist (u v) = dist (w v) + 1. Also, since \min plus one" was applied,we have P 0(u) P (w) + 1. Now,P 0(u) ; P (v) ; dist (u v) (P (w) + 1) ; P (v) ; (dist (w v) + 1)= P (w) ; P (v) ; dist (w v)and hence the (v) does not increase in this case. The second case to consider is when uhas changed its value by applying the \max minus one" part of the rule.
The reasoning inthis case is similar: let w be a neighbor of u with P (w) = P 0(u) + 1. Clearly, dist (w v) dist (u v ) + 1. This implies thatP 0(u) ; P (v) ; dist (u v) (P (w) ; 1) ; P (v) ; (dist (w v) ; 1)= P (w) ; P (v) ; dist (w v)and we are done.As noted above, the inequality in (24.14) is strict if (u) > 0. In other words, each timea node with positive potential changes its pulse number, its potential decreases. This fact,when combined with Lemmas 8 and 9, immediately implies eventual stabilization. However,using this argument leads to a proof that the stabilization time is bounded by the totalpotential of the conguration, which in turn depends on the initial pulse assignment.
Weneed a stronger argument in order to prove a bound on the stabilization time that dependsonly on the topology. Toward this end, we dene the notion of \wavefront".345De nition 4 Let v be any node in the graph with potential (v). The wavefront of v, denoted(v), is dened by(v) = minfdist (u v ) j P (u) ; P (v ) ; dist (u v ) = (v )g :u2VIn the graphical representation, the wavefront of a node is simply the distance to theclosest node of on the \potential line" (see Figure 24.9 for an example). Intuitively, onecan think of (v) as the distance to the \closest largest trouble" of v. The importance ofthe wavefront becomes apparent in Lemma 12 below, but let us rst state an immediateproperty it has.Lemma 11 Let v 2 V . Then (v) = 0 if and only if (v) = 0.Lemma 12 Let v be any node with (v) > 0, and let 0(v) be the wavefront of v after onetime unit.
Then 0 (v ) (v ) ; 1.Proof: Suppose (v) = f > 0 at some state. Let u be any node such that P (u) ; P (v) ;dist (u v) = (v ), and dist (u v ) = f . Consider a neighbor w of u which is closer to v ,i.e., dist (w v) = f ; 1 (it may be the case the w = v). From the denition of (v), itfollows that P (w) < P (u) ; 1. Now consider the next time in which w applies Rule 24.13.If at that time (v) < f , we are done. Otherwise, w must assign P (w) P (u) ; 1.
Nogreater value can be assigned, or otherwise Lemma 10 would be violated. At this time,P (w) ; P (v) ; dist (w v) = (v) also, and hence (v) f ; 1.Corollary 13 Let v be any node. Then after (v) time units, (v) = 0.We can now prove the main theorem.Theorem 14 Let G = (V E ) be a graph with diameter d, and let P : V ! N be a pulseassignment. Applying Rule 24.13 above results in a legal conguration in d time units.Proof: By Lemma 9, it suces to show that after d time units, (v) = 0 for all v 2 V .From Corollary 13 above, we actually know that a slightly stronger fact holds: for all nodev 2 V , after (v) time units, (v) = 0. The theorem follows from the facts that for allv 2 V , (v) d, and by the fact that (v) never increases, by Lemma 10.24.4.1 Implementation with Bounded Pulse NumbersThe optimal rule from above works only when the pulse numbers may grow unboundedly.However, we can use the reset protocol to make is work with bounded-size registers.
Supposethat the registers dedicated to the pulse numbers may hold the values 0 : : : B , for some boundB . Then the protocol would work by proceeding according to the unbounded rule (Eq. 24.13),and whenever a value should be incremented above B , reset is invoked. Notice that we mustrequire that B is suciently large, to enable propper operation of the protocol between346resets: if B is less than the diameter of the network, for instance, then there is a possiblescenario in which the far nodes never get to participate in the protocol.3476.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchDecember 10, 1992Lecture 25This is the last lecture of the course: we didn't have time to cover a lot of materialwe intended to.
Some of the main topics missing are fault-tolerant network algorithms andtiming-based computing. We'll have several additional lectures in January to cover some ofthis, for those who are interested. Today, we'll do one major result in fault-tolerant networkalgorithms, namely the impossibility of fault-tolerant consensus in asynchronous networks.We'll also do two other results on ways to get around this limitation.25.1 Fischer-Lynch-Paterson Impossibility ResultRecall the consensus problem from the shared memory work. The interface is dened bythe input actions init i(v), and output actions decide i(v), where i is a process and v is avalue.
Here we shall consider the same init-decide interface, but the implementation is nowa distributed network algorithm. The message delivery is FIFO, and completely reliable. Infact, we will assume that the nodes have reliable broadcast actions, so that when a nodesends a message, it is sent simultaneously to all the others, and because of the reliability ofmessage transmission, it will eventually get there. We consider solving this problem in theface of processor faults since we are giving an impossibility result, we consider only a verysimple kind of faulty behavior | at most one stopping failure.
(Using such a weak kind offault makes the impossibility result stronger.)The impossibility of solving consensus in such a friendly environment is rather surprising.The story is that Fischer, Lynch and Paterson worked on this problem for some while,trying to get a positive result (i.e., an algorithm). Eventually, they realized that there was avery fundamental limitation getting in the way.
They discovered an inherent problem withreaching agreement in an asynchronous system, in the presence of any faulty process.The Model. As in any impossibility result, it is very important to dene precisely theassumptions made about the underlying model of computation. Here we assume that thenetwork graph is complete, and that the message system consists of fair FIFO queues.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
