Distributed network optimization problems, such as minimum spanning tree, minimum cut, and shortest path, are an active research area in distributed computing. This paper presents a fast distributed algorithm for such problems in the CONGEST model, on networks that exclude a fixed minor. On general graphs, many optimization problems, including the ones mentioned above, require Ω(√ n) rounds of communication in the CONGEST model, even if the network graph has a much smaller diameter. Naturally, the next step in algorithm design is to design efficient algorithms which bypass this lower bound on a restricted class of graphs. Currently, the only known method of doing so uses the low-congestion shortcut framework of Ghaffari and Haeupler [SODA'16]. Building off of their work, this paper proves that excluded minor graphs admit high-quality shortcuts, leading to an O(D^2) round algorithm for the aforementioned problems, where D is the diameter of the network graph. To work with excluded minor graph families, we utilize the Graph Structure Theorem of Robertson and Seymour. To the best of our knowledge, this is the first time the Graph Structure Theorem has been used for an algorithmic result in the distributed setting. Even though the proof is involved, merely showing the existence of good shortcuts is sufficient to obtain simple, efficient distributed algorithms. In particular, the shortcut framework can efficiently construct near-optimal shortcuts and then use them to solve the optimization problems. This, combined with the very general family of excluded minor graphs, which includes most other important graph classes, makes this result of significant interest.
Work on global network problems in the distributed setting was started by Gallager, Humblet and Spira @cite_26 who gave a @math -round algorithm to compute the MST. The algorithm was subsequently improved by Awerbuch @cite_5 to an optimal'' @math rounds. However, Peleg and Awerbuch @cite_19 noted that a more useful notion of round complexity would parametrize on both the number of nodes @math and the diameter @math since @math for many practical networks. This influenced a substantial amount of work that followed, culminating in an @math distributed algorithm for many optimizations problems in the CONGEST setting. Examples of such problems include the MST @cite_1 @cite_40 @cite_13 , @math -approximate Maximum Flow @cite_35 , Minimum Cut @cite_31 @cite_28 , Shortest Paths, and Diameter @cite_20 @cite_0 @cite_18 @cite_30 @cite_16 @cite_32 @cite_2 @cite_6 @cite_42 . The mentioned @math round complexity is for all of these problems, as there exists a family of graphs for which any algorithm must take a matching @math rounds @cite_25 @cite_33 .
@cite_30 @cite_35 @cite_42 @cite_2 @cite_5 @cite_20 @cite_18 @cite_26 @cite_28 @cite_32 @cite_6 @cite_19 @cite_40 @cite_16 @cite_25 @cite_33 @cite_1 @cite_0 @cite_31 @cite_13
2107282727 2952482095 2053788000 2040011014 2592613193 2077371116 37512724 1976927627 2949588463 1984090926 2163097371 2076983944 1508113861
Given a simple graph G=(V,E) and a set of sources S ⊆ V, denote for each node ν e V by Lν(∞) the lexicographically ordered list of distance source pairs (d(s,v),s), where s ∈ S. For integers d,k ∈ N∪ ∞ , we consider the source detection, or (S,d,k)-detection task, requiring each node v to learn the first k entries of Lν(∞) (if for all of them d(s,v) ≤ d) or all entries (d(s,v),s) ∈ Lν(∞) satisfying that d(s,v) ≤ d (otherwise). Solutions to this problem provide natural generalizations of concurrent breadth-first search (BFS) tree constructions. For example, the special case of k=∞ requires each source s ∈ S to build a complete BFS tree rooted at s, whereas the special case of d=∞ and S=V requires constructing a partial BFS tree comprising at least k nodes from every node in V. In this work, we give a simple, near-optimal solution for the source detection task in the CONGEST model, where messages contain at most O(log n) bits, running in d+k rounds. We demonstrate its utility for various routing problems, exact and approximate diameter computation, and spanner construction. For those problems, we obtain algorithms in the CONGEST model that are faster and in some cases much simpler than previous solutions. We present a near-optimal distributed algorithm for @math -approximation of single-commodity maximum flow in undirected weighted networks that runs in @math communication rounds in the model. Here, @math and @math denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of @math , and it nearly matches the @math round complexity lower bound. The development of the algorithm contains two results of independent interest: (i) A @math -round distributed construction of a spanning tree of average stretch @math . (ii) A @math -round distributed construction of an @math -congestion approximator consisting of the cuts induced by @math virtual trees. The distributed representation of the cut approximator allows for evaluation in @math rounds. All our algorithms make use of randomization and succeed with high probability. This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a sensitive decomposable function (e.g. majority, parity, maximum, OR, AND). The main problem considered is the problem of finding the MST. This problem, which has been known for at least 9 years, is one of the most fundamental and the most studied problems in the field of distributed network algorithms. Any algorithm for any one of the problems above requires at least O( E + V log V ) communication and O( V ) time in the general network. In this paper, we present new algorithms, which achieve those lower bounds. The best previous algorithm requires T( E + V log V ) in communication and T( V log V ) in time. Our result enables to improve algorithms for many other problems in distributed computing, achieving lower bounds on their communication and time complexities. A distributed network is modeled by a graph having n nodes (processors) and diameter D. We study the time complexity of approximating weighted (undirected) shortest paths on distributed networks with a O (log n) bandwidth restriction on edges (the standard synchronous CONGEST model). The question whether approximation algorithms help speed up the shortest paths and distance computation (more precisely distance computation) was raised since at least 2004 by Elkin (SIGACT News 2004). The unweighted case of this problem is well-understood while its weighted counterpart is fundamental problem in the area of distributed approximation algorithms and remains widely open. We present new algorithms for computing both single-source shortest paths (SSSP) and all-pairs shortest paths (APSP) in the weighted case. Our main result is an algorithm for SSSP. Previous results are the classic O(n)-time Bellman-Ford algorithm and an O(n1 2+1 2k + D)-time (8k⌈log(k + 1)⌉ --1)-approximation algorithm, for any integer k ≥ 1, which follows from the result of Lenzen and Patt-Shamir (STOC 2013). (Note that Lenzen and Patt-Shamir in fact solve a harder problem, and we use O(·) to hide the O(poly log n) term.) We present an O (n1 2D1 4 + D)-time (1 + o(1))-approximation algorithm for SSSP. This algorithm is sublinear-time as long as D is sublinear, thus yielding a sublinear-time algorithm with almost optimal solution. When D is small, our running time matches the lower bound of Ω(n1 2 + D) by Das (SICOMP 2012), which holds even when D=Θ(log n), up to a poly log n factor. As a by-product of our technique, we obtain a simple O (n)-time (1+ o(1))-approximation algorithm for APSP, improving the previous O(n)-time O(1)-approximation algorithm following from the results of Lenzen and Patt-Shamir. We also prove a matching lower bound. Our techniques also yield an O(n1 2) time algorithm on fully-connected networks, which guarantees an exact solution for SSSP and a (2+ o(1))-approximate solution for APSP. All our algorithms rely on two new simple tools: light-weight algorithm for bounded-hop SSSP and shortest-path diameter reduction via shortcuts. These tools might be of an independent interest and useful in designing other distributed algorithms. The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in O(n) time, where n is the number of vertices in the input graph G. Peleg and Rubinovich, FOCS'99, showed a lower bound of Ω(D + √n) for this problem, where D is the hop-diameter of G. Whether or not this problem can be solved in o(n) time when D is relatively small is a major notorious open question. Despite intensive research that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires O((n logn)5 6) time, for D = O(√n logn), and O(D1 3 #183; (n logn)2 3) time, for larger D. This running time is sublinear in n in almost the entire range of parameters, specifically, for D = o(n log2 n). We also generalize our result in two directions. One is when edges have bandwidth b ≥ 1, and the other is the s-sources shortest paths problem. For the former problem, our algorithm provides an improved bound, compared to the unit-bandwidth case. In particular, we provide an all-pairs shortest paths algorithm that requires O(n5 3 #183; log2 3 n) time, even for b = 1, for all values of D. For the latter problem (of s sources), our algorithm also provides bounds that improve upon the previous state-of-the-art in the entire range of parameters. From the technical viewpoint, our algorithm computes a hopset G″ of a skeleton graph G′ of G without first computing G′ itself. We then conduct a Bellman-Ford exploration in G′ ∪ G″, while computing the required edges of G′ on the fly. As a result, our algorithm computes exactly those edges of G′ that it really needs, rather than computing approximately the entire G′. Distributed distance oracles consist of a labeling scheme which assigns a label to each node and a local data structure deployed to each node. When a node v wants to know the distance to a node u, it queries its local data structure with the label of u. The data structure returns an estimated distance to u, which must be larger than the actual distance but can be overestimated. The accuracy of the distance oracle is measured by stretch, which is defined as the maximum ratio between actual distances and estimated distances over all pairs (u, v). This paper is concerned with distributed algorithm for finding shortest paths in an asynchronous communication network. For the problem of Breadth First Search, the best previously known algorithms required either T( V ) time, or T ( E + V · D ) communication. We present new algorithm, which requires O ( D 1+e ) time, and O ( E 1+e ) messages, for any e > 0. (Here, V is number of nodes, E is number of edges and D is the diameter.) This constitutes a major step towards achieving the lower bounds, which are O( E ) communication and O( D ) time. For the general (weighted) shortest paths problem, previously known shortest-paths algorithms required O ( k · V 2 ) messages and O ( V · log k V ) time. Our algorithm requires O ( E 1 + e · log W ) messages and O ( V 1 + e · log W ) time. Our results enable to improve significantly solutions for other basic network problems (e.g. leader election). We study approximate distributed solutions to the weighted all-pairs-shortest-paths (APSP) problem in the CONGEST model. We obtain the following results. @math A deterministic @math -approximation to APSP in @math rounds. This improves over the best previously known algorithm, by both derandomizing it and by reducing the running time by a @math factor. In many cases, routing schemes involve relabeling, i.e., assigning new names to nodes and require that these names are used in distance and routing queries. It is known that relabeling is necessary to achieve running times of @math . In the relabeling model, we obtain the following results. @math A randomized @math -approximation to APSP, for any integer @math , running in @math rounds, where @math is the hop diameter of the network. This algorithm simplifies the best previously known result and reduces its approximation ratio from @math to @math . Also, the new algorithm uses uses labels of asymptotically optimal size, namely @math bits. @math A randomized @math -approximation to APSP, for any integer @math , running in time @math and producing compact routing tables of size @math . The node lables consist of @math bits. This improves on the approximation ratio of @math for tables of that size achieved by the best previously known algorithm, which terminates faster, in @math rounds. The design of distributed approximation protocols is a relatively new and rapidly developing area of research. However, so far, little progress has been made in the study of the hardness of distributed approximation. In this paper we initiate the systematic study of this subject and show strong unconditional lower bounds on the time-approximation trade-off of the distributed minimum spanning tree problem, and show some of its variants. This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter @math . This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sublinear in n, but linear in @math (specifically, @math for @math ). Our result is achieved through the application of graph decomposition and edge-elimination-by-pipelining techniques that may be of independent interest. Abstract. We consider the problem of routing messages between pairs of nodes of a distributed network, along shortest paths. We introduce a new routing technique, called Distance Routing that, due to its structure, is naturally well applicable on a family of networks called Series Parallel Graphs. We compute the time and space complexities of Distance Routing in Series Parallel Graphs, and we compare them with the relative complexities of Interval Routing, showing the improvement of Distance Routing especially in terms of time complexity. We study the problem of computing the minimum cut in a weighted distributed message-passing networks (the CONGEST model). Let λ be the minimum cut, n be the number of nodes (processors) in the network, and D be the network diameter. Our algorithm can compute λ exactly in (O(( n ^ * n +D) ^4 ^2 n) ) time. To the best of our knowledge, this is the first paper that explicitly studies computing the exact minimum cut in the distributed setting. Previously, non-trivial sublinear time algorithms for this problem are known only for unweighted graphs when λ ≤ 3 due to Pritchard and Thurimella’s O(D)-time and O(D + n 1 2log* n)-time algorithms for computing 2-edge-connected and 3-edge-connected components [ACM Transactions on Algorithms 2011].