Distributed Shortest Paths Algorithms (Extended Abstract)
Distributed Shortest Paths Algorithms(Extended Abstract)Baruch Awerbuch *Dept. of Mathematics and Lab. for Computer Science,M.I.T.,Cambridge, MA ormedThis paper is concerned with distributedalgorithm for finding shortest paths in an asynchronous communicationnetwork. For the problem of Breadth First Search, the bestpreviously known algorithms required either O(V) time, orO(E V .D) communication.We present new algorithm,which requires O(# ‘)time, and O(E1 C) messages, forany c 0. (Here, V is number of nodes, E is number ofedges and D is the diameter.)This constitutesa majorstep towards achieving the lower bounds, which are 0(E)communicationand Q(D) time.For the general (weighted) shortest paths problem, previously known shortest-paths algorithmsrequiredO(k. V”)and O(V . log, V) time.Our algorithmrequiresO(E’ ” . log W) messages and O(V’ ’ . log W) time.Our results enable to improve significantlysolutionsformessagesother basic networkI1.1problems(e.g. leader election).and complexityfast.Thus,we willbe interestedc., is the upper bound on the numberof messagessent in any execution of 7 . The Time Complexity off,IntroductionModelrelativelyin minimizingthe message exchange,as well as timeof control algorithms. We deal exclusively with worstcase performance of the algorithm.Given execution of a protocol in an asynchronousnetwork, the longest message delay in that execution isthe maximum difference between arrival and transmission times of a message, in terms of some global clock(which is not accessible to nodes). Following [Gal82],normalized time between two events in an executionis the ratio between the physical time between thosetwo events in terms of the global clock above, and thelongest message delay in that execution, i.e. physicaltime in case that link delays vary between 0 and 1. Incontext of asynchronous network, “time” always means“normalized time”.The CommunicationComplexity of ?F, denoted bydenoted by t,,timemeasures1.2This paper is concerned with distributedalgorithmsin an asynchronous communicationnetwork.Thosealgorithms may be repeated many times in case thatthe network’s topology changes. From the point ofview of network’s performance, it is desirable that themessages of the control algorithms don’t occupy muchof the network bandwidth,and that such algorithms isof 7r.The problemsWe consider the problem of finding shortest paths inthe communicationgraph G(V, E) of the network. Inthe “undirected”version of the problem, we are interested in finding shortest paths in an undirected graphG, (V, E, UJ) from all nodes to an a distinguishednodes s E V, where w is an assignment of non-negativeweights we to edges e E E.The BFS problem is the special case of shortestpaths, where w(e) 1, for all e E E. The “directed” version of the problem is defined similarly,except that we look for shortest paths in a directed graph@ (v, E) which is an orientationof G(V, E), i.e.(i j) E i? implies that (i - j) E E.Those problems appear to be fairly basic in the fieldof distributednetwork protocols. The major application for shortest paths tree is that shortest paths treea given source node can be used for routingw.r.t.*Supportedby Air Force ContractTNDGAFOSR86-0078,AR0 contract DAAL03-86-K-0171,NSF contract CCR8611442,and a special grant from IBM.Permission to copy without fee all or part of this material is grantedprovided that the copies are not made or distributed for directcommercial advantage, the ACM copyright notice and the title ofthe publication and its date appear, and notice is given that copyingTois be permission of the Association for Computing Machinery.copy otherwise,or to republish,requires a fee and/or specificpermission.@ 1989 ACM O-89791-307-8/t19/0005/0490is the upper bound on on normalizedof any execution 1 SO490
of data from other nodes to the source node, in thecheapest possible way.Improving efficiency of distributedShortest Paths(BFS) yields improvement in more complex distributedalgorithms,in which Shortest Paths (BFS) appearsto be the bottleneck.Examples of such problems aregiven in section 2.Observe that a shortest paths problem on networkG (V, E, w) can be reduced to a BFS problem onan “expanded” network & (v’, ,6?) where an edgee is substitutedby a path containing w, edges andWe - 1 “dummy nodes”. The difficulty with this reduction is that the numbe r of nodes in the expandednetwork is huge, namely IV1 O(W . V), where W isthe maximal edge weight. Using Gabow’s scaling technique, one can effectively guarantee W 5 lV[. However, with Gabow’s technique or without it, in eithercase [VI IV1 and 121 ]E]. Thus, existence of ablack bot performing BFS with linear complexity, O(k)messages, only guarantees O(E . V) messages shortestpaths algorithm, which is far from satisfactory.2Contributionsof thisFigure ime1k . V2ViiEl ’ . log W[Awe851[Fre85]This paperOuralgorithmsCommunicationAuthorv -log, vviiV’ ’algorithmsversus. log Wexistingones.e.g. the ARPANET[MRR80], where D V. Thehigh (R(V)) time overhead is inherent for that method.The best known algorithmin terms of time isachieved by applying synchronizer y of [Awe851 to theobvious synchronous algorithm.This algorithm (symbolically attributed to [Awe85]) requires O(E V.D.k)messages and O(logk V . D) time, for any h. It meetsthe lower bound in time but is quite inefficient in communication.The new BFS algorithm requires O(E’ ‘)messagesand O(Dl ‘)time, for all E 0, thus making a steptowards achieving the lower bounds.The followingFigure 1 summarizes results of this paper, comparingthem to existing results.paperWe present new distributedalgorithms for the aboveproblems with sharply improved bounds on communication and time.Our algorithmis based on novel synchronizationtechnique, which proceeds recursively.Even thoughthe algorithm is just a composition of very simple modular blocks, its analysis is non-trivial.To overcomethe difficulties, we introduce novel counting methods,based on notions of amortized complexities.2.1OurD . log, VV1 cD’fCE V.k.DE ’El ’[Awe853[AG85]This paperFigure tPathsThere have been a number of works on shortest pathsin the past [Ga182], [Jaf80]. The best previously knownshortest-pathsalgorithms is obtained using the SYNCHRONIZER of to [Awe85]. It requires O(E . V”) messages and O( V. log, V) t ime. (This does not count thepreprocessing phase of [Awe85].)For planar graphsonly, the algorithm of Frederickson achieves O(V1i)message and time.Using the scaling techniques of Gabow [Gab851 andthe BFS algorithmin this paper, we obtain a newshortest paths algorithm,which requires O(E1 C .log W) messages and 0( V’ ’ . log W) time.The following Figure 2 summarizes our improvements over existing algorithms.for BFSThe obvious lower bounds on communicationand timecomplexities of distributedBFS algorithms are Cl(E)messages and 0(D) time, where E is the number ofnetwork edges, and D is the diameter,In the synchronozls network, the obvious algorithm meets thoselower bounds. However, the situation is much morecomplex in the asynchronous network, where the bestknown algorithms exhibit trade-o in terms of communication and time complexities.The best known algorithm in terms of communication is due to [AG85]. It requires @(El ‘) messagestime, for all E 0. [AG85] is “relativelyand @(V1 ‘)close” to the lower bound in communication.However,as advocated by Peleg [Pe187], this algorithm is quiteinefficient in time, in case that D V. Peleg [Pe187]points out that the difference between O(V) and O(D)time can be very significant in many existing anningotherTree,problemsGlobalE’unc-One of the most well-studied problems in thefield of distributednetwork algorithms is the problem491
Author3C0mln1 cation )3.1 ;qFJFigure mpactRoutingTables:For the purpose of constructing compact routing tables, the best current algorithm due to Peleg and Upfal [PUSS] uses networkpartitionalgorithms,which are modificationsof thesynchronizer-iniiializalionalgorithm of [Awe85]. BFSis the bottleneck in this algorithm.Organizationof thisDIJKSTRAalgorithmLet us first outline a simple BFS algorithm, which willbe (symbolically)referred to as the DIJKSTRA Algorithm, because of its similarity with Dijkstra’s shortestpath algorithm and Dijkstra-Sholtendistributed termination detection procedure [DS80].The algorithm maintains a tree rooted at the sourcenode. Initially, the tree is empty. Upon terminationofthe algorithm, the tree is the desired BFS tree. Thruout the algorithm, the tree can only grow, and at anytime it is a sub-tree of the final BFS tree. The algorithm operates in successive iterations, each processinganother BFS layer. At the beginning of a given iteration 1, the tree has been constructed for all nodes inlayers m 1. Upon the terminationof iteration 1, thetree will be extended by one layer, covering also allnodes in layer I.The purpose of the source node is to control theseiterations by means of a synchronizationprocess, performed over the tree. This enables the source node todetect the time that the tree has been completed upto distance 1 and thus iteration I 1 can be started.The source node triggers each iteration by broadcasting message over the tree which is forwarded outto nodes at layer 1 - 1 in the tree. Upon receipt ofthis message, the latter nodes send “exploration”messages to all neighbors, carrying label I- 1, and tryingto discover nodes at layer 1.When a node receives explorationmessage from aneighbor, it acts as follows. If this is the first exploration message that the node has seen, it chooses thesender of the message as its parent, sets its distancelabel to be 1 plus distance label of the sender, andsends back a “positive”acknowledgment(ack) to thesender, indicating that the sender was chosen as a parent. Upon receipt of subsequent exploration messages,the node sends back to sender “negative” ack, indicating that it already has parent. Upon receiving apositive ack, a node adds the sender to its list of children.When a node at layer 1 - 1 receives acks to all exploration messages it has sent, it sends an ack to itsparent in the BFS forest, indicating whether any newdescendants have been discovered. When an internalnode gets such acks from all children, it sends an ackto its parent. Eventually, all the acks are collected bythe source node. This implies that layer 1 has beenprocessed completely. If any nodes have been discovered at that layer, the next iteration I 1 is started.Otherwise, the algorithm terminates.The complexities of this algorithm are O(V - D E)of finding a leader in a network.It is equivalent tothe problem of finding a spanning tree. Leader election is an importanttool for breaking symmetry in adistributedsystem. Constructionof a spanning treeor finding a leader appears as a building block essentially in every complex network protocol, and is closelyrelated to many problems in distributedcomputing.There are many problems which are provably equivalent [Awe87] to the problem of electing a leader, interms of the communicationand time complexities.One example of such problems is a class of so-called“global sensitive” functions [Awe87], e.g. MAXIMUM,SUM, PARITY, MAJORITY, COUNTING, OR, AND.The best known leader election algorithms have beengiven in [Awe87], [Pel87]. F’eleg [Pe187] advocates forleader election algorithms w’hose running time dependsonly on the diameter of the :network. While Peleg’salgorithms achieves optimal O(D) time, its communication complexity is O(E . 0).Using the new BFS algorithmin this paper, wecan improve significantlytime performance of existingleader election algorithms.We achieve almost linear(in diameter) time and almost linear communication.Our improvements are shown in following Figure 3.2.4BasicspaperIn this extended abstract, we only deal with BFS algorithms. We leave the extensions to the Shortest Paths,Leader Election, etc., for the full paper. Although ourBFS algorithms is in fact very simple, it has a recursive structure, which makes it hard to conceive it as awhole.In the following Section 3 we describe the basic toolsused. In Section 4 we outline main ideas behind ourimprovement,and provide more details in Sections 5,6, 7, 8, 9. In Section 10 we analyze complexity of thealgorithm.492
SourcesStrip,SourcesLeadeFigure 4:StripMethod.Figure 5:messages and O(P)time, where d is the number oflayer being processed, Indeed, there are D iterationsand in each of them synchronizationis performed overBFS tree which requires O(V) messages and O(D)time. In addition, one exploration message is sent overeach edge once in each direction.The overhead due to synchronizationmakes this algorithm quite inefficient in sparse and long networks,where E V . D. If one considers a network with allnodes on a single path of length V- 1, one sees that thecommunicationand time complexity are each O(V’).Obviously, the performance of the algorithm degradesas the number D of layers to be processed atedwitha cluster.of layers in the strip and the number of sources in thestrip. Using this technique, with strips of size d I/%,we can achieve O(D1.5) time and O(E . fi)communication. This strategy, with some additional improvements, has been used in [AG87], and in [Fre85].We are looking for more efficient reduction strategy.In sequential setting, one can easily reduce the problem with multiple sources to the problem with a singlesource, by connecting each one of the sources to someauxiliary (“root”)source node via edges of weight 0,or simply contract all the sources into a single source.In a distributed setting, this method does not work.paradigm3.3It is easy to reduce the problem where big number oflayers needs to be processed to problem where smallnumber of layers needs to be processed. If the network has diameter D, we can conceptually“cut” thenetwork into “strips” of length d, and process thosestrips sequentially, like in the following Figure 4.Our strategy now is to cut the network into strips ofsize d D, and process those strips one after another,thus extending the BFS tree. We know also whichedges lead to nodes in previous strip, so that messagesare not sent along those edges.For the purpose of processing the strip, we need tocreate BFS forest rooted at the all nodes on the border of the strip. Thus, we have multiple source nodes,rather than single source node.The most naive reduction from the case of multiplesources to the case of single source is to find separatelyshortest paths w.r.t.each one of sources, and then“combine” those shortest paths in an obvious manner.However, this strategy is of order of magnitude of thenumber of nodes in the cluster.Unfortunately,thismethod may introduce a blow-up factor to the communication complexity, which grows with the numberSourcecontractionparadigmHowever, whenever we encounter the a multiplesources problem, we will always have available some“cover tree”, spanning all those nodes. For example,there is a legitimate cover tree spanning a11the sourcenodes of a strip, namely the (whole) BFS tree spanning all the previous strips.The cover tree can beused to synchronize between source nodes, thus effectively “contracting”them into a single (super-)node, orcluster. With each cluster, we associate the followingdistributed data structures:lSource nodes of the cluster.lCover tree which spans all the source nodes.lBFS forest which spans all the sources.We can use those data structures in order to run DIalgorithm for the case of multiple sources asif it were run in the case of single source. The basicidea is that the algorithm proceeds in iterations, controlled by the “root”. The synchronizationover covertree enables the root to detect that all the sources havecompleted their trees up to a certain BFS layer. TheJKSTRA493
ber of problemsand size.root node notifies all the sourc.es about the beginningof the iteration by broadcasting message over the covertree. .Upon receiving this messages, each source nodenode runs one iteration of DIJKSTRA algorithm, as described above. When a source node collects all its acksto messages over BFS tree rooted at itself, its task iscomplete. The source node will send ack towards theroot of the cover tree after it has completed its task,and after it receives acks from all its children. Nodespropagate acks in this manner, until the root node hasreceived acks to all the messages that it has sent. Now,new iteration can start.Clearly, the communicationoverhead of synchronization will grow with the sire of the cover tree, whiletime overhead of synchronizationwill grow with thedepth of the cover tree, i.e. the length of a longestpath from a node to the root. We conclude that inorder for the resulting algorithm is efficient, the size ofcover tree should not be much bigger than the the stripbeing processed, both in terms of the size and depth.Observe that, initially, we have a cover tree for thestrip, which is the whole BFS tree. It has depth ofe(D) and size of O(V), i.e. is way too big and toolong. The natural strategy is to reduce hard problemsto easy problems. In order to do this, we have to reducethe original problem with “biig” cover tree and “big”processing length, to “not too many” new problemswith “big” cover tree and “big” processing length.As noticed in [AG85], we can treat separately different connected components in the strip, since treesgrown in different components do not interfere witheach other. Thus, the algorityhm of [AG85] was tryingto construct a spanning tree cd each connected component of the strip. The difficulty here is that the set ofnodes belonging to the strip is not known in advance;we know where the strip “sta:rts”, but we do not knowwhere it “ends”. If one knows in advance where thestrip “ends”, ‘the problem solved in [AG85] is trivialized.An algorithm proposed in [AG85] enables to construct recursively spanning trees of each strip. Thisstrategy guarantees that cover tree have small number of nodes, but, unfortunately,tend to have very bigdepth. The reason for this is that a connected component of a strip of depth cl does not necessarily havea spanning tree of depth d. In fact, it might be thecase that the whole strip is connected, and that anytree that will span all the source nodes of the strip willhave Q(V) depth, causing Q(V) time overhead. Sincethis method inherently requiires Q(V) time overhead,it is inadequate for us. It is worth pointing out that[AG85] focused only on communication.The main contributionof this paper is the reductionof the problem with big cover tree to “moderate” num-depthCoverStrip3.4with cover trees of “moderate”Definition3.1 Given a strip with d BFS layers, a stripcover is a forest of node-disjointtrees, which span all thesourceby thesubsetby thenodes in the strip. A collection of clusters inducedcover is a set of subsets of source nodes, eachconsisting of the set of all source nodes spannedsame tree of the cover.Definition3.2 For an arbitraryfine the followingload f&or:withinde-is the maximal number of clusters which aredistance d from some node in the strip.depth factor. is the maximaldivided by d.size:strip cover (forest)parameters:is the numberdepth of a tree in the cover,of trees in the cover.Our task would have been significantlysimplified,if, prior to processing this strip, some “oracle” wouldgive us a “good” strip cover, for which both load factorand depth factor being “small”. We can then processthe strip “efficiently”by contractingall the sourcesspanned by the same tree into a single cluster, andthen performing BFS independentlyfrom each cluster.The intuition here is that load factor is the reason forcommunicationblow-up, as it upper-bounds the number of different clusters competing for th
2.2 Improvements for Shortest Paths There have been a number of works on shortest paths in the past [Ga182], [Jaf80]. The best previously known shortest-paths algorithms is obtained using the SYN- CHRONIZER of to [Awe85]. It requires O(E . V”) mes- sages and O( V. log, V) t ime. (This does not count the
The classical K -Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for v ehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely
Dr. Haim Levkowitz Fall, 2007 Graph Algorithms: Chapters 24-25 Part 3: Shortest paths. 2 Shortest Paths Chapter 24: Single-source Chapter 25: All-pairs. 3 Shortest Paths Chapter 24: Single-source. 4 How to find shortest route between two
1 Finding Top-k Shortest Paths with Diversity Huiping Liu, Cheqing Jin , Bin Yang, and Aoying Zhou Abstract—The classical K Shortest Paths (KSP) problem, which identifies the kshortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services.
General Constrained Shortest k-Disjoint Paths (GCSDP(k)) Problem: Given two nodes s and t and a positive integer T, the GCSDP(k) problem is to find a set of k(k ‚ 2) link-disjoint s-t paths p1;p2:::;pk such that the delay of each path pi is at most T and the total cost of the k paths is minimum. Constrained Shortest k-Disjoint Paths (CSDP(k .
shortest one. Yen (1971) first introduced a k-shortest path searching method by deleting node from the network, and then several k-shortest algorithms have been suggested. There are two groups of k-shortest path algorithm. The difference is one allow loops in result paths and another don’t. In transportation network the latter is always used .
Our algorithm takes the hierarchy-based approach invented by Thorup. Key words. single-source shortest paths, all-pairs shortest paths, undirected graphs, Dijkstra’s algorithm AMS subject classifications. 05C12, 05C85, 68R10 DOI. 10.1137/S0097539702419650 1. Introduction. The problem of computing shortest paths is indisputably one
—RedLeader[DreweHenley],Star Wars () All-Pairs Shortest Paths .Introduction In the previous chapter, we discussed several algorithms to find the shortest paths from a single source vertex s to every other vertex of the graph, by const
Study program Administrimi Publik (2012/2013) Fakulteti Shkencat Shoqërore Bashkëkohore Cikli i studimeve Cikli i parë (Deridiplomike) SETK 180 Titulli I diplomuar në administrim publik Numri në arkiv i akreditimit [180] 03-671/2 Data akreditimit 22.06.2012 Përshkrimi i programit Programi i Administratës publike ka një qasje multidiciplinare të elementeve kryesore të studimit në .
