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

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

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

Note that there must exist such a path, because the leadersthat need to communicate are in adjacent clusters (and each cluster is connected). We needsome preprocessing to determine these paths we ignore this issue for now.We need also to specify, for the nal implementation, where the cluster-OK action occurs.This is done as an output from some node in the cluster-synch protocol if synchronizer is used, it is an output of the root of the spanning tree of the cluster. It is also an input tothe leader node in the forest-synch for that same cluster.

If these two are the same node,then this action just becomes an internal action of the actual node in the distributed system.(If these node are dierent, then we need to have them communicate along some path, alsodetermined by some preprocessing this requires an extra piece of the implementation.)The formal structure of this hybrid algorithm is quite nice: each node in the distributednetwork is formally an IOA which is the composition of two other IOA's, one for each of thetwo protocols (intra-cluster and inter-cluster synchronizers).

We can consider two orthogo258nal decompositions of the entire implementation: vertical (i.e., to nodes and channels), orhorizontal (i.e., by the two algorithms, each distributed one piece per node).Analysis. We shall consider the specic implementation where the cluster-synch is doneusing , and the forest-synch is done using , and we assume that the leader for within acluster is same node that serves as the root for .Consider one round.

The number of messages is O(n) for the work within the clusters,plus O(E 0), where E 0 is the number of edges on all the paths needed for communication amongthe leaders. We remark that depending on the decomposition, E 0 could be signicantlysmaller than E . The time complexity is proportional to the maximum height of any clusterspanning tree.Thus, the optimal complexity of the hybrid algorithm boils down to the combinatorialproblem of nding a graph decomposition such that both the sum of the path lengths and themaximum height are small.

Also, we need to establish this decomposition with a distributedalgorithm. We will not address these problems here.20.2.5 ApplicationsWe can use the synchronizers presented above to simulate any synchronous algorithm (inthe original model for synchronous systems presented earlier in the course) on an asynchronous system. Note that the synchronizer doesn't work for fault-tolerant algorithms suchas Byzantine agreement, because it is not possible in this case to wait for all processes.Ring leader election algorithms such as LeLann-Chang, Hirshberg-Sinclair, and Petersoncan thus be run in an asynchronous system. But note that the message complexity goes wayup if we do this.

Since they already worked in an asynchronous system without any suchextra synchronization, this isn't interesting. The following applications are more interesting.Network leader election. Using the synchronizer, the algorithm that propagates the maximal ID seen so far can work as in the synchronous setting. This means that it can countrounds as before, waiting only diam rounds before terminating. It also means that the number of messages doesn't have to be excessive: it's not necessary for nodes to send constantly,since each node now knows exactly when it needs to send (once to each neighbor at eachasynchronous round). Using synchronizer , the complexity of the resulting algorithm isO(diam ) time, and O(E diam ) messages, which is better than the aforementioned naivestrategy of multiple spanning trees.Breadth-rst search.

For this problem, the synchronizer proves to be a big win. Recallthe horrendous performance of the Bellman-Ford algorithm in the asynchronous model, andhow simple the algorithm was in the synchronous setting. Now we can run the synchronous259algorithm using, say synchronizer , which leads to an O(E diam ) message, O(diam ) timealgorithm. (Compare with the synchronous algorithm, which needed only O(E ) messages.)Note: O(E diam ) might be considered excessive communication. We can give a directasynchronous algorithm based on building the BF tree in levels, doing broadcast-convergecastat each level, adding in the new leaves for that level, and terminating when no new nodes arediscovered.

For this algorithm, the time is then O(diam 2), which is worse than the algorithmbased on the synchronizer. But the message complexity is only O(E + n diam ), since eachedge is explored once, and tree edges are traversed at most a constant number of times foreach level. It is also possible to obtain a time-communication tradeo by combining the twostrategies. More specically, we can explore k levels in each phase using , obtaining time2ndiamcomplexity of O( diamk ) and communication complexity of O(E k + k ), for 1 k diam .Weighted Single-source Shortest Paths.

Using the synchronous algorithm with synchronizer yields an algorithm with O(n) time complexity, and O(En) messages. We remarkthat there is an algorithm with fewer messages and more time (cf. Gabow, as developed byAwerbuch in his notes).Maximal Independent Set. We can apply the synchronizer to a randomized synchronousalgorithm like MIS too. We omit details.20.3 Lower Bound for SynchronizersAwerbuch's synchronizer result suggests that a synchronous algorithm can be converted intoa corresponding asynchronous algorithm without too great an increase in costs.

In particular,by using synchronizer , it is possible not to increase the time cost at all. The followingresult by Arjomandi-Fischer-Lynch shows that this approach cannot be adopted universally.In particular, it establishes a lower bound on time for an asynchronous algorithm to solvea particular problem. Since there is a very fast synchronous algorithm for the problem,this means that not every fast synchronous algorithm can be converted to an asynchronousalgorithm with the same time complexity. Note that the dierence is not caused by requiringany fault-tolerance, so the result may seem almost contradictory to the synchronizer results.We start by dening the problem. Let G = (V E ) be a graph. Recall that diam (G)denotes the maximum distance between two nodes in G. The system's external interfaceconsists of ash i output actions, for all i 2 V , where ash i is an output of the I/O automatonat node i.

As an illustration, imagine that the ash i is a signal that node i has completedsome task. Dene a session as a sequence of ashes in which at least one ash i occurs forevery i. We can now dene the k-session problem: we require simply that the algorithmshould perform at least k disjoint sessions.260The original motivation for this setting was that the nodes were performing some kindof coordinated calculation on external data, e.g., a Boolean matrix transitive closure, in thePRAM style. Each node (i j k) was responsible for writing a 1 in location (i j ), in caseit ever saw 1's in both locations (i k) and (k j ).

Notice that for this problem, it doesn'tmatter whether the nodes do excessive checking and writing. Correctness is guaranteed ifwe have at least log n sessions (i.e., if there is \enough" interleaving).The reason the problem is stated this way is that it is a more general problem than thesimpler problem in which all processes do exactly one step in each session (so it strengthensthe impossibility result). Note also that this is a weak problem statement: it doesn't evenrequire the nodes to know when k sessions have completed.Before we turn to prove the lower bound result, let us make the problem statementmore precise.

As usual, we model the processes as IOAs, connected by FIFO channels. Forsimplicity, we let the node automata partition consist of a single-class (intuitively, the nodesare executing sequential programs).Our goal is to prove an inherent time complexity result. (Note that this is the rst lowerbound on time that we are proving in this course.) We need to augment the model byassociating times, as usual, with the events, in a monotone nondecreasing way (approachinginnity in an innite fair execution).

Let l be a bound for local step time, and d be the boundfor delivery of rst message in each channel. (This is a special case of the general notion oftime bounds for IOA's.) We assume that d l. An execution with times associated withevents satisfying the given requirements is called a timed execution.Next, we dene the time measure T (A) for algorithm A as follows.

For each execution of the algorithm, dene T () to be the supremum of the times at which a ash event occursin . (There could be innitely many such events, hence we use a supremum here.) Finally,we deneT (A) = sup(T ()) :We can now state and prove our main result for this sectionTheorem 2 Suppose A is an algorithm that solves the k-session problem on graph G. ThenT (A) (k ; 1) diam (G) d.Before we turn to prove the theorem, consider the k-session problem in the synchronous case.We can get k sessions without the nodes ever communicating | each node just does a ashat every round, for k rounds. The time would be only kd (for a time measure normalized sothat each round counts for d time).

This discrepancy proves that the inherent multiplicativeoverhead due to asynchrony for some problems is proportional to diam (G).Proof Sketch: (of Theorem 2)By contradiction. Suppose that there exists an algorithm A with T (A) < (k ; 1) diam (G) d.261Call a timed execution slow if all the actions take their maximum times, i.e., if the deliveriesof the rst messages in the channels always takes time d and the step times always take l.Let be any slow (fair) timed execution of the system. By the assumption that A is correct, contains k sessions. By the contradiction assumption, the time of the last ash in isstrictly less than (k ; 1) diam (G) d.

So we can write = 000, where the time of thelast event in 0 is less than (k ; 1) diam (G) d, and where there are no ash events in 00.Furthermore, because of the time bound, we can decompose 0 = 12 : : :k;1 where eachof the r has the dierence between the times of its rst and last events strictly less thandiam (G) d.We now construct another fair execution of the algorithm, = 12 : : : k;1 00. Thiswill be an ordinary untimed fair execution that is, we do not assign times to this one. Theexecution is constructed by reordering the actions in each r (and removing the times) toobtain r , and by removing the times from 00 to get 00.

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

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