Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed comp...
详细信息
Motivated by the increasing need to understand the algorithmic foundations of distributed large-scale graph computations, we study a number of fundamental graph problems in a message-passing model for distributed computing where k >= 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is an (almost) optimal distributed randomized algorithm for graph connectivity. Our algorithm runs in (O) over tilde (n/k(2)) rounds ((O) over tilde notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of (O) over tilde (n/k) [Klauck et al., SODA 2015] and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of (Omega) over tilde (n/k(2)). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. Using the connectivity algorithm as a building block, we then present fast randomized algorithms for computing minimum spanning trees, (approximate) min-cuts, and for many graph verification problems. All these algorithms take (O) over tilde (n/k(2)) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of (Omega) over tilde (n/k(2)) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.
We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a ...
详细信息
ISBN:
(纸本)9781450357951
We present a randomized distributed algorithm that computes a A coloring in any non-complete graph with maximum degree A > 4 in 0 (log A) + 20 (/log log n) rounds, as well as a randomized algorithm that computes a A-coloring in 0((log log n)2) rounds when A E [3, 0(1)]. Both these algorithms improve on an 0 (log3 n/log A) round algorithm of Panconesi and Srinivasan [STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Q (log log n) round lower bound of Brandt et al. [STOC'16].
In classic distributedgraph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Delta + 1)-list-colorings of the graph), and the task of distributed algorithm is to construct ...
详细信息
ISBN:
(纸本)9781450357951
In classic distributedgraph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Delta + 1)-list-colorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information. We study distributed sampling and counting problems, in which each instance specifies a joint distribution of feasible solutions. The task of distributed algorithm is to sample from this joint distribution, or to locally measure the volume of the probability space via the marginal probabilities. The latter task is also known as inference, which is a local counterpart of counting. For self-reducible classes of instances, the following equivalences are established in the LOCAL model up to polylogarithmic factors: For all joint distributions, approximate inference and approximate sampling are computationally equivalent. For all joint distributions defined by local constraints, exact sampling is reducible to either one of the above tasks. If further, sequentially constructing a feasible solution is trivial locally, then all above tasks are easy if and only if the joint distribution exhibits strong spatial mixing. Combining with the state of the arts of strong spatial mixing, we obtain efficient sampling algorithms in the LOCAL model for various important sampling problems, including: an O(root Delta log(3) n)-round algorithm for exact sampling matchings in graphs with maximum degree Delta, and an O(log(3) n)-round algorithm for sampling according to the hardcore model (weighted independent sets) in the uniqueness regime, which along with the Omega(diam) lower bound in [3] for sampling according to the hardcore model in the non-uniqueness regime, gives the first computational phase transition for distributed sampling.
Restricting the bandwidth in models of distributedgraph computations naturally introduces challenges that arise due to communication bottlenecks. In this talk, I will survey techniques for proving lower bounds on the...
详细信息
ISBN:
(纸本)9781450357951
Restricting the bandwidth in models of distributedgraph computations naturally introduces challenges that arise due to communication bottlenecks. In this talk, I will survey techniques for proving lower bounds on the complexity of fundamental graph problems under limited bandwidth. For some problems, allowing relaxed solutions can significantly reduce the required amount of communication, enabling efficient computations. Two successful approaches for overcoming provable barriers, namely, approximations and testing, will be exemplified and discussed in the context of distributed computing.
Coordination is essential for dynamic distributed systems whose components exhibit interactive and autonomous behaviors. Spatially distributed, locally interacting, propagating computational fields are particularly ap...
详细信息
Coordination is essential for dynamic distributed systems whose components exhibit interactive and autonomous behaviors. Spatially distributed, locally interacting, propagating computational fields are particularly appealing for allowing components to join and leave with little or no overhead. Computational fields are a key ingredient of aggregate programming, a promising software engineering methodology particularly relevant for the Internet of Things. In our approach, space topology is represented by a fixed graph-shaped field, namely a network with attributes on both nodes and arcs, where arcs represent interaction capabilities between nodes. We propose a SMuC calculus where calculus-like modal formulas represent how the values stored in neighbor nodes should be combined to update the present node. Fixpoint operations can be understood globally as recursive definitions, or locally as asynchronous converging propagation processes. We present a distributed implementation of our calculus. The translation is first done mapping SMuC programs into normal form, purely iterative programs and then into distributed programs. Some key results are presented that show convergence of fixpoint computations under fair asynchrony and under reinitialization of nodes. The first result allows nodes to proceed at different speeds, while the second one provides robustness against certain kinds of failure. We illustrate our approach with a case study based on a disaster recovery scenario, implemented in a prototype simulator that we use to evaluate the performance of a recovery strategy.
In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D subset of V with the property that every vertex in V \ D is adjacent to at least 2 vertices of D. We are inter...
详细信息
In this paper we consider the 2-dominating set problem (2MDS). We look for a smallest subset of vertices D subset of V with the property that every vertex in V \ D is adjacent to at least 2 vertices of D. We are interested in the distributed complexity of this problem in the local model, where the nodes have no identifiers but there is a port ordering available. We propose a distributed local (constant time) algorithm yielding a 6-approximation in the class of planar graphs. Earlier result shows that in this case, for any is an element of > 0, there is no deterministic distributed local/constant-round algorithm providing.a (5-is an element of)-approximation of the 2MDS. (C) 2016 Elsevier B.V. All rights reserved.
We present a randomized distributed algorithm that computes a minimum spanning tree in tau(mix)(G) . 2(O(root log n log log n))) rounds, in any n-node graph G with mixing time tau(mix)(G). This result provides a sub-p...
详细信息
ISBN:
(纸本)9781450349925
We present a randomized distributed algorithm that computes a minimum spanning tree in tau(mix)(G) . 2(O(root log n log log n))) rounds, in any n-node graph G with mixing time tau(mix)(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated (Omega) over tilde (D + root n) lower bound of Das Sarma et al. [STOC' 11] which holds for some worst-case general graphs. The core novelty in this result is a distributed method for permutation routing. In this problem, one is given a number of source-destination pairs, and we should deliver one packet from each source to its destination, all in parallel, in the shortest span of time possible. Our algorithm allows us to route and deliver all these packets in tau(mix)(G) .2(O(root log n log log n)) rounds, assuming that each node v is the source or destination for at most d(G)(v) packets. The main technical ingredient in this routing result is a certain hierarchical embedding of good-expansion random graphs on the base graph, which we believe can be of interest well beyond this work.
We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers o...
详细信息
ISBN:
(纸本)9781538634646
We present a deterministic distributed algorithm that computes a (2 Delta - 1)-edge-coloring, or even list-edgecoloring, in any n-node graph with maximum degree Delta, in O(log(8) Delta . log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g., Open Problem 4 in the distributedgraph Coloring book of Barenboim and Elkin. The previous best round complexities were 2(O(root log n)) by Panconesi and Srinivasan [STOC' 92] and (O) over tilde (root Delta) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS' 16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2 Delta - 1)-edgecoloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Delta, this algorithm computes a maximal matching in O(r(5) log(6+log r) Delta . log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkin's book, a ((log Delta/epsilon)(O(log 1/epsilon)) - round deterministic algorithm for (1 + epsilon)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting lambda-arboricity graphs with out-degree at most inverted right perpendicular (1 + epsilon)lambda inverted left perpendicular, for any constant epsilon > 0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.
Computing a Maximal Independent Set (MIS) is a central problem in distributed graph algorithms. This paper presents an improved randomized distributed algorithm for computing an MIS in an all-to-all communication dist...
详细信息
ISBN:
(纸本)9781450349925
Computing a Maximal Independent Set (MIS) is a central problem in distributed graph algorithms. This paper presents an improved randomized distributed algorithm for computing an MIS in an all-to-all communication distributed model, known as the congested clique model, defined as follows: Given a graph G = (V, E), initially each node knows only its neighbors. Communication happens in synchronous rounds over a complete graph, and per round each node can send O(logn) bits to each other node. We present a randomized algorithm that computes an MIS in (O) over tilde (log Delta/root log + 1) <= (O) over tilde(root log Delta rounds of congested clique, with high probability. Here Delta denotes the maximum degree in the graph. This improves quadratically on the O(log Delta algorithm of [Ghaffari, SODA' 16]. The core technical novelty in this result is a certain local sparsification technique for MIS, which we believe to be of independent interest.
We present a simple deterministic distributed (2 vertical bar c) approximation algorithm for minimum weight vertex cover, which Delta completes in O(log Delta/epsilon log log A) rounds, where A is the maximum degree i...
详细信息
ISBN:
(纸本)9781450339643
We present a simple deterministic distributed (2 vertical bar c) approximation algorithm for minimum weight vertex cover, which Delta completes in O(log Delta/epsilon log log A) rounds, where A is the maximum degree in the graph, for any epsilon > 0 which is at most O(1). For a constant c, this implies a constant approximation in O(log Delta/ log log Delta) rounds, which contradicts the lower bound of [KMW10].
暂无评论