1,721,045 research outputs found
Fast Distributed Algorithms for Connectivity and MST in Large Graphs
Full text linkMotivated 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 gg 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(n/k2) rounds (~O notation hides a polylog(n) factor and an additive polylog(n) term). This improves over the best previously known bound of ~O(n/k) [Klauck et al., SODA 2015], and is optimal (up to a polylogarithmic factor) in view of an existing lower bound of ~Ω(n/k2). Our improved algorithm uses a bunch of techniques, including linear graph sketching, that prove useful in the design of efficient distributed graph algorithms. 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(n/k2) rounds, and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of ~Ω(n/k2) for many graph verification problems using lower bounds in random-partition communication complexity
Fast distributed algorithms for connectivity and MST in Large Graphs
Full text link
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 Õ(
n
/
k
2
) rounds (Õ notation hides a polylog(
n
) factor and an additive polylog(
n
) term). This improves over the best previously known bound of Õ(
n
/
k
) [Klauck et al., SODA 2015] and is optimal (up to a polylogarithmic factor) in light of an existing lower bound of Ω
˜
(
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 Õ(
n
/
k
2
) rounds and are optimal up to polylogarithmic factors. We also show an almost matching lower bound of Ω
˜
(
n
/
k
2
) rounds for many graph verification problems by leveraging lower bounds in random-partition communication complexity.
</jats:p
A time- and message-optimal distributed algorithm for minimum spanning trees
Full text linkThis paper presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ(D + √n) time and exchanges Õ(m) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω(D + √n) [Elkin, SIAM J. Comput. 2006] and the message lower bound of Ω(m) [Kutten et al., J. ACM 2015], which both apply to randomized Monte Carlo algorithms.The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both Ω(D + √n) rounds and Ω(m) messages
Ballast: A ball-based algorithm for structural motifs
Full text linkStructural motifs encapsulate local sequence-structure-function relationships characteristic of related proteins, enabling the prediction of functional characteristics of new proteins, providing molecular-level insights into how those functions are performed, and supporting the development of variants specifically maintaining or perturbing function in concert with other properties. Numerous computational methods have been developed to search through databases of structures for instances of specified motifs. However, it remains an open problem how best to leverage the local geometric and chemical constraints underlying structural motifs in order to develop motif-finding algorithms that are both theoretically and practically efficient. We present a simple, general, efficient approach, called Ballast (ball-based algorithm for structural motifs), to match given structural motifs to given structures. Ballast combines the best properties of previously developed methods, exploiting the composition and local geometry of a structural motif and its possible instances in order to effectively filter candidate matches. We show that on a wide range of motif-matching problems, Ballast efficiently and effectively finds good matches, and we provide theoretical insights into why it works well. By supporting generic measures of compositional and geometric similarity, Ballast provides a powerful substrate for the development of motif-matching algorithms.Published versio
Robust computation of aggregates in wireless sensor networks: Distributed randomized algorithms and analyses
No full textA wireless sensor network consists of a large number of small, resource-constrained devices and usually operates in a hostile environment that is prone to link and node failures. Consequently, the algorithms developed on a sensor network have to be prudent on energy cost, scalable to network size, and robust to frequent topology changes. Among the operations on a sensor network, computing aggregates such as average, minimum, maximum and sum over the data stored in the sensor nodes is not only an important application in itself but also fundamental to various other functions such as system monitoring, data querying, and collaborative information processing. In this work, we present a class of distributed randomized algorithms to efficiently compute aggregates in a sensor network. The proposed algorithms are energy-efficient, scalable, and robust to frequent topology changes. Our analyses and experimental results show that they outperform other representative distributed algorithms for the aggregates computation in wireless sensor networks
Distributed approximation algorithms for minimum spanning trees and other related problems with applications to wireless ad hoc networks
No full textDue to the advent of various advanced network technologies, distributed algorithms have become an important and rapidly growing field of research. Many emerging networks such as wireless ad hoc networks and peer-to-peer networks operate under inherent resource constraints (energy, bandwidth, etc.). Topologies of these networks can also change dynamically. For these networks, it is necessary to develop efficient (in both time and message complexities) distributed algorithms even if the solutions are sub-optimal (approximate). In this dissertation, we develop and analyze a class of distributed approximation algorithms to solve two fundamental network optimization problems: minimum spanning trees (MST) and minimum-cost k-connected subgraphs. We design and analyze a simple randomized scheme called Nearest Neighbor Tree (NNT) for efficient construction of approximate MSTs. We show that our scheme constructs a O(log n)-approximate MST in any weighted graph and a constant approximation for uniform distribution of nodes on a plane. Then we apply the NNT scheme to design local distributed algorithms for MST in complete networks, arbitrary networks, and wireless ad hoc networks. Our main contribution is the first non-trivial distributed O(log n)-approximation algorithm for MST in an arbitrary network which takes Õ(D + L) time and Õ(E) messages, where L is a parameter called the local shortest path diameter and D is the (unweighted) diameter of the graph. L always lies between 1 and n but can be much smaller than [special characters omitted] in most of the graphs. In addition, we develop an algorithm for a complete graph that takes O(log n) time and expected O(n log n) messages and an algorithm for wireless ad hoc network that takes O(log2 n) time and expected O(n) messages. We also perform extensive simulations of our algorithms for wireless ad hoc networks. Simulations validate the theoretical results and show that the bounds can be much better in practice. We extend the NNT scheme to develop a simple randomized scheme for constructing low-cost k-connected spanning subgraphs in a weighted complete graph. We show that our algorithm gives an approximation ratio of O(klog n) for a metric graph, O(k) for a random graph with nodes uniformly randomly distributed in [0,1]2 and O(log [special characters omitted]) for a graph with random edge weights U(0,1). We then design an efficient local distributed algorithm for constructing a k-connected spanning subgraph (for any k ≥= 1) in a point-to-point distributed model, where the processors form a complete network. This algorithm takes O(log [special characters omitted]) time and expected O(nk log [special characters omitted]) messages
- …
