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

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

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

Now, our plan is to trace backwards the longest sequential chainof message-sends that had to be sent in order to produce a leader.Let us denote the eventual winner by P 0. In the nal phase of the algorithm, P 0 had tohear from two active counterclockwise neighbors, P 1 and P 2. In the worst case, the chainof messages sent from P 2 to P 0 is actually n in length, and P 2 = P 0, as depicted in Figure18.3.Now, consider the previous phase.

We wish to continue pursuing the dependency chainbackwards from P 2 (which might be the same node as P 0). The key point is that, forany two consecutive phases, it must be the case that between any two active processes inthe later phase, there is at least one active process in the previous phase. Thus, at thenext-to-last phase, there must have been an additional process in the interval starting fromP 1 counterclockwise to P 2, and another additional process in the interval starting from P 0counterclockwise to P 1.Thus, the chain of messages pursued backward from P 2 in the next-to-last phase, fromP 3 and P 4, can at worst only extend as far as P 1 (i.e., in the worst case, P 1 = P 4), asdepicted in Figure 18.4. And there is an additional process Q1 between P 1 and P 0.At the phase preceding the next-to-last phase, P 4 waits to hear from P 5 and P 6, whereP 6 is at worst equal to Q1 also, there is an additional process Q2 between Q1 and P 0 (see225P0=P2P1Figure 18.3: The last phase of the Peterson algorithm.

P 0 is the winner.P0P3Q1P1=P4Figure 18.4: The next-to-last phase of the Peterson algorithm.Figure 18.4). At the phase before this, P 6 waits to hear from P 7 and P 8, etc. This analysiscan go on, but we never get back around to P 0, and so the total length of the dependencychain is at worst 2n. We conclude therefore that the time is at most around 2 nd.18.1.4 Burns' Lower Bound ResultAll the algorithms in the previous section are designed to minimize the number of messages,and the best achieve O(n log n) communication. Recall that in the synchronous case, we hada matching (n log n) lower bound under the assumption that the algorithms are comparisonbased.

That carries over to the asynchronous model, since the synchronous model can beformulated as a special case of the asynchronous model. Note that the algorithms towhich this lower bound applies are not allowed to use the UIDs in arbitrary ways, e.g., forcounting. As we saw, if we lift this restriction, then we can get O(n) message algorithms in226P0Q2P3P6=Q1P5P4Figure 18.5: The next preceding phase of the Peterson algorithm.the synchronous model.It turns out, however, that the asynchronous network model has enough extra uncertaintyso that the (n log n) lower bound applies regardless of how the identiers are used. Theproof of this fact is completely dierent proof from the synchronous case: now the asynchronyis used heavily.

We consider leader election algorithms with the following properties. The number of nodes in the ring is unknown. Bidirectional channels. Asynchronous model. Unbounded identier set. Any node may be elected as leader.For this setting, Burns proved the following result.Theorem 2 Any leader election algorithm with the properties listed above sends at least14 n log n messages in the worst case, where n is the number of processes in the ring.For simplicity, we assume that n is a power of 2.

(The proof can be extended to arbitraryn: cf. homework.) We model each process as an I/O automaton, and stipulate that eachautomaton is distinct (in essence, that each process has a unique identier). The automatoncan be represented as in Figure 18.6. Each process has two output actions, send-right andsend-left, and two input actions, receive-right and receive-left.Our job will ultimately be to see how a collection of automata of this type behave whenarranged into a ring however, in the course of this exploration we would also like to seehow the automata behave when arranged not in a ring, but simply in a straight line, as in227receive-left-send-leftsend-right-receive-rightFigure 18.6: A process participating in a leader election algorithm.------Figure 18.7: A line of leader-electing automata.Figure 18.7.

Formally, we can say that a line is a linear composition (using I/O automatoncomposition) of distinct automata, chosen from the universal set of automata.The executions of such a line of automata can be examined \in isolation", where thetwo terminal automata receive no input messages in this case the line simply operates onits own. Alternatively, we might choose to examine the executions of the line when certaininput messages are provided to the two terminal automata.As an added bit of notation, we will say that two lines of automata are compatible whenthey contain no common automaton between them. We will also dene a join operation ontwo compatible lines which simply concatenates the lines this operation interposes a newmessage queue to connect the rightmost receive-right message of the rst line with theleftmost send-left message of the second, and likewise to connect the leftmost receive-leftmessage of the second line with the rightmost send-right message of the rst, and then uses228ordinary IOA composition.

Finally, the ring operation on a single line interposes new queuesto connect the rightmost send-right and leftmost receive-left actions of the line, and therightmost receive-right and leftmost send-left actions. The ring and join operations aredepicted graphically in Figure 18.8.LMjoin(L,M)Lring(L)Figure 18.8: The join and ring operations.We proceed with a proof that 41 n log n messages are required to elect a leader in a bidirectional asynchronous ring, where n is unknown to the processes and process identiers areunbounded.

For a system S (line or ring), and an execution of S , we dene the followingnotions. COMM (S ) is the number of messages sent in execution of system S . COMM (S ) = sup COMM (S ). Here we consider the number of messages sentduring any execution of S . For lines, we only consider executions in which no messagescome in from the ends. A state q of a ring is quiescent if there is no execution fragment starting from q inwhich any new message is sent. A state q of a line is quiescent if there is no execution fragment starting from q in whichno messages arrive on the incoming links at the ends, and in which any new messageis sent.We now state and prove our key lemma.229Lemma 3 For every i 0, there is an innite set of disjoint lines, Li , such that for all L2 Li, j L j= 2i and COMM (L) 1 + 14 i2i.Proof: By induction on i.Base case: For i = 0, we need an innite set of dierent processes such that each cansend at least 1 message without rst receiving one.

Suppose, for contradiction, that thereare 2 processes, p and q, such that neither can send a message without rst receiving one.Consider rings R1, R2, and R3 as shown in Figure 18.9.pR1R2R3pqqFigure 18.9: Basis for proof of Lemma 15.1In all three rings, no messages are ever sent, so each process proceeds independently.Since R1 solves election, p must elect itself, and similarly for R2 and q.

Then R3 electstwo leaders, a contradiction. It follows that there is at most one process that can't send amessage before receiving one. If there is an innite number of processes, removing one leavesan innite set of processes that will send a message without rst receiving one. Let L0 bethis set, which proves the basis.Inductive step: Assume the lemma is true for i ; 1. Let n = 2i .

Let L, M , N be any 3lines from Li;1 . Consider all possible combinations of two of these lines into a line of doublesize: LM , LN , ML, NL, MN , and NM . Since innitely many disjoint sets of three linescan be chosen from Li;1 , the following claim implies the lemma.Claim 4 At least one of the 6 lines can be made to send at least 1 + n4 log n messages.Proof: Assume that the claim is false. By the inductive hypothesis, there exists a niteexecution L of L for which COMM (L L) 1 + n8 log n2 , and in which no messages arrivefrom the ends.We can assume without loss of generality that the nal conguration of L is quiescent,since otherwise L can be extended to generate more messages, until the number 1+ n4 log n ofmessages is reached. We can assume the same condition for M and N by similar reasoning.230LMcan know about joinFigure 18.10: join (L M )Now consider any two of the lines, say L and M .

Consider join (L M ). Consider an executionthat starts by running L on L and M on M , but delays messages over the boundary.In this execution there are at least 2(1 + n8 log n2 ) messages. Now deliver the delayedmessages over the boundary. By the assumption that the claim is false, the entire line mustquiesce without sending more than n4 additional messages, messages, for otherwise the totalexceeds 2(1 + n8 log n2 ) + n4 = 2 + n4 log n.

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

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