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

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

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

Note that, unfortunately, this timebound has a d n term, regardless of the load, and this might be big.Resiliency: LeLann discusses various types of resiliency in his paper. Process failure: If a process stops and announces its failure, the rest of the processes canrecongure the ring to bypass the failed process. This requires a distributed protocol.Note that a process that doesn't announce its failure can't be detected as failed, sincein an asynchronous system, there is no way for a process to distinguish a failed processfrom one that is just going very slowly.

Loss of token: When a token loss is detected (e.g., by timeout), a new one can begenerated by using a leader-election protocol, as studied earlier.Lamport's algorithmAnother solution uses Lamport logical time. In particular, the state machine simulationapproach is applied. The state machine here has as its state a queue of process indices,which is initially empty. The operations are try i and exit i, where try i has the eect ofadding i to the end of queue and exit i has the eect of removing i from queue , providedit is at the front. When user i initiates a try i or exit i event, it is regarded as submittinga corresponding \update" request. Then, as described above, the state machine approachbroadcasts the updates, waits to be able to perform them, i.e., a node can perform an updatewhen that update has the smallest timestamp of any update in the request buer, and thenode knows it has all the smaller timestamp updates.

When the node is able to perform theupdate, it does so. The replicated object state is used as follows. When the queue at nodei gets i at the front, the process at node i is allowed to do a crit i. When the queue at node275i gets i removed, the process at node i is allowed to do a rem i .Let us now argue that this algorithm guarantees mutual exclusion. Suppose not saypi and pj are simultaneously in C , and suppose, without loss of generality, that pi has thesmaller timestamp. Then when j was added to pj 's queue, the state machine implementationensures that i must have already been there, ahead of j . But i has not been removed (sinceit is still in C ). So j could not have done a crit i action, a contradiction.It is a little hard to analyze the algorithm in this form, since it combines three protocols:the logical time generation protocol, the replicated state machine protocol, and the extrarules for when to do crit and rem actions.

We can merge and \optimize" these protocolssomewhat as follows. Assume that the logical time generation is done according to Lamport'salgorithm, based on the given messages. We combine the request-buer and the simulatedstate machine's state. Also, the ack messages below are used as the dummy messagesdiscussed in the general approach.In this algorithm, every process pi maintains a local variable region as before, and for eachother process pj a local queue queue j .

This queue j contains all the messages ever receivedfrom pj (we remark that this can be optimized). There are three types of messages: try-msg(i): Broadcast by pi to announce that it is trying. exit-msg(i): Broadcast by pi to announce that it is exiting. ack(i): Sent by pi to pj , acknowledging the receipt of a try-msg(j ) message.The code is written so as to send all these messages at the indicated times. We assumethat the sending or broadcast logical times are piggybacked on the messages, and the queuescontain these logical times as well as the messages themselves. Also, the logical time of eachof the broadcast events (for try or exit requests) is used as the timestamp of the correspondingupdate.This already tells what messages are sent and when.

We won't have a separate applicationstep to apply the update to the queue, since we do not have an explicit representation of thequeue. All we need now is rules for pi telling when to perform crit i and rem i actions. Belowwe give these rules. pi ! R : Can be done anytime after exit i occurs. pi ! C : Must ensure that region = T and that the following conditions hold.1. Mutual exclusion is preserved.2.

There is no other request pending with a smaller timestamp.276Process pi can ensure that the above conditions are met by checking for each j 6= i:1. Any try-msg in queue j with timestamp less than the timestamp of the currenttry ; msg of pi has an exit-msg in queue j with a larger timestamp than that ofj 's try-msg.2. queue j contains some message (possibly an ack) with timestamp larger than thetimestamp of the current try-msg of piLamport's algorithm has the following properties.Mutual Exclusion. This can be proven by contradiction as follows.

Assume that twoprocesses, pi and pj , are in C at the same time, and (without loss of generality) that thetimestamp of pi 's request is smaller than the timestamp of pj 's request. Then pj had tocheck its queue i in order to enter C . The second test and FIFO behavior of channels implythat pj had to see pi 's try-msg, so by the rst test it had also to see an exit-msg from pi , sopi must have already left C .Lockout-freedom. This property results from servicing requests in timestamp order. Sinceeach event (in particular, request event) has a nite number of predecessors, all requests willeventually get serviced.Complexity. Let us rst deal with the number of messages.

We shall use amortizedanalysis here as follows. Every request involves sending try-msg, ack and exit-msg messagesbetween some process and all the others, thus 3(n ; 1) messages are sent per request. Forthe time complexity, note that when there is a single request in the system, the time is2d + O(s), where d is the communication delay and s is the local processing time. We assumethat the broadcast is done as one atomic step if n ; 1 messages are treated separately, theprocessing costs are linear in n, but these costs are still presumed to be small comparedto the communication delay d.

(Recall that, in contrast, the time complexity of Lelann'salgorithm had a dn term.)2776.852J/18.437J Distributed AlgorithmsLecturer: Nancy LynchDecember 1, 1992Lecture 2222.1 Mutual Exclusion (cont.)Last time, we gave Lamport's mutual exclusion algorithm based on his state-machine approach. Recall that we have try and exit messages as input to the state machine, andack messages to respond to try messages. The following two variants provide interestingoptimizations of this algorithm.22.1.1 Ricart & Agrawala (1981)Ricart and Agrawala's algorithm uses only 2(n ; 1) messages per request. It improvesLamport's original algorithm by acknowledging requests in a careful manner that eliminatesthe need for exit messages. This algorithm uses only two types of messages: try and OK.Process pi sends try (i) as in Lamport's algorithm, and can go critical after OK messageshave been received from all the others.

So the interesting part is a rule for when to sendan OK message. The idea is to use a priority scheme. Specically, in response to a try, aprocess does the following. Replies with OK if it is not critical or trying. If it is critical, it defers the reply until it exits, and then immediately sends all thedeferred OKs. If it is trying, it compares the timestamp of its own request to the timestamp of theincoming try. If its own is bigger, its own is interpreted as lower priority, and the processsends OK immediately else (having higher priority) the process defers acknowledgingthe request until it nishes with its own critical region.In other words, when there is some conict, this strategy is to resolve it in favor of the\earlier" request, as determined by the timestamps.278Properties of the Ricart-Agrawala Algorithm.Mutual Exclusion: Proved by contradiction.

Assume that processes pi and pj are bothin C and (without loss of generality) that the timestamp of pi 's request is smaller than thetimestamp of pj 's request. Then there must have been try and OK messages sent from eachto the other, prior to their entry to C at each node, the receipt of the try precedes thesending of the matching OK.

But there are several possible orderings of the various events(see Figure 22.1).Process iProcess jjtry−try−iOK−i−jOKFigure 22.1: A possible scenario for the Ricart-Agrawala algorithm.Now, the timestamp of i is less than that of j , and the logical time of the receipt of j 'stry by i is greater than the timestamp of j 's request (by the logical time property). So itmust be that the receipt of pj 's try message at i occurs after pi has broadcast its try. Thenat the time pi receives pj 's try, it is either trying or critical. In either case, pi 's rules say ithas to defer the OK message, thus pj could not be in C , a contradiction.Deadlock-freedom is also proved by contradiction.

Assume some execution that reaches apoint after which no progress is achieved. That is, at that point all the processes are eitherin R or T , none are in C , and from that point on, no process changes regions. By goinga little further out in the execution, we can also reach a point after which no messages areever in transit. Among all the processes in T after that point, let pi be the process havingthe request message with the lowest timestamp. Then since pi is blocked forever it must bebecause some other process pj has not returned an OK message to it.

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

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