More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinat...
详细信息
More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributedalgorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks. (C) 2020 The Author(s). Published by Elsevier B.V.
distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or o...
详细信息
distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: aproverthat assigns acertificateto each node, and a distributed algorithm called averifierthat is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between thesize of the certificatestored at every node, and thenumber of roundsof the verification protocol.
We give a distributed algorithm in the CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (Proceedings of the 30th International S...
详细信息
We give a distributed algorithm in the CONGEST model for property testing of planarity with one-sided error in general (unbounded-degree) graphs. Following Censor-Hillel et al. (Proceedings of the 30th International Symposium on distributed Computing, pp. 43-56, 2016), who recently initiated the study of property testing in the distributed setting, our algorithm gives the following guarantee: For a graph G = (V, E) and a distance parameter epsilon, if G is planar, then every node outputs accept, and if G is epsilon-far from being planar (i.e., more than epsilon . vertical bar E vertical bar edges need to be removed in order to make G planar), then with probability 1 - 1/poly(n) at least one node outputs reject. The algorithm runs in O(log vertical bar V vertical bar . poly(1/epsilon)) rounds, and we show that this result is tight in terms of the dependence on vertical bar V vertical bar. Our algorithm combines several techniques of graph partitioning and local verification of planar embeddings. Furthermore, we show how a main subroutine in our algorithm can be applied to derive additional results for property testing of cycle-freeness and bipartiteness, as well as the construction of spanners, in minor-free (unweighted) graphs.
distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of (Omega) over tilde(root n+ D) rounds for several global problems, where n denotes the number of nodes and D t...
详细信息
distributed graph algorithms in the standard CONGEST model often exhibit the time-complexity lower bound of (Omega) over tilde(root n+ D) rounds for several global problems, where n denotes the number of nodes and D the diameter of the input graph. Because such a lower bound is derived from special "hard-core" instances, it does not necessarily apply to specific popular graph classes such as planar graphs. The concept of low-congestion shortcuts was initiated by Ghaffari and Haeupler [SODA2016] for addressing the design of CONGEST algorithms running fast in restricted network topologies. In particular, given a graph class C, an f -round algorithm for constructing shortcuts of quality q for any instance in C results in (O) over tilde (q+ f)-round algorithms for solving several fundamental graph problems such as minimum spanning tree and minimum cut, for C. The main interest on this line is to identify the graph classes allowing the shortcuts that are efficient in the sense of breaking (O) over tilde(root n + D)-round general lower bounds. In this study, we consider the relationship between the quality of low-congestion shortcuts and the following four major graph parameters: doubling dimension, chordality, diameter, and clique-width. The key ingredient of the upper-bound side is a novel shortcut construction technique known as short-hop extension, which might be of independent interest.
The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained o...
详细信息
We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is kn...
详细信息
We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius(G, t), that extends the standard graph theoretical notion of radius, for considering all the ways in which t nodes may crash, and we present an algorithm that solves consensus in radius(G, t) rounds. Then we derive a lower bound showing that, among oblivious algorithms, our algorithm is optimal for a large family of graphs including all vertex-transitive graphs.(c) 2023 Elsevier Inc. All rights reserved.
We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, whic...
详细信息
We introduce TeraHAC, a (1+ε)-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing (1+ε)-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of (1+ε)-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is *** evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.
We present improved distributedalgorithms for variants of the triangle finding problem in the CONGEST modeL We show that triangle detection, counting, and enumeration can be solved in (O) over tilden(1/3)) rounds usi...
详细信息
We present improved distributedalgorithms for variants of the triangle finding problem in the CONGEST modeL We show that triangle detection, counting, and enumeration can be solved in (O) over tilden(1/3)) rounds using expander decompositions. This matches the triangle enumeration lower bound of (Omega) over tilde (n(1/3)) by Izumi and Le Gall [PODC'17] and Pandurangan, Robinson, and Scquizzato [SPAA'18], which holds even in the CONGESTED-CLIQUE model. The previous upper bounds for triangle detection and enumeration in CONGEST were (O) over tilde (n(2/3)) and (O) over tilde (n(3/4)), respectively, due to Izumi and Le Gall [PODC'17]. An (epsilon, phi)-expander decomposition of a graph G = (V, E) is a clustering of the vertices V = V-1 boolean OR ... boolean OR V-x such that (i) each cluster V;induces a subgraph with conductance at least phi and (ii) the number of inter-cluster edges is at most epsilon vertical bar E vertical bar. We show that an (epsilon, phi)-expander decomposition with phi = (epsilon/ log n)(2o(k)) can be constructed in O(n(2/k) . poly(1/phi, log n)) rounds for any epsilon is an element of (0, 1) and positive integer k. For example, a (1/n(o(1)), 1/n(o(1)))-expander decomposition only requires n(o(1)) rounds to compute, which is optimal up to subpolynomial factors, and a (0.1. 1/poly log n)-expander decomposition can be computed in O (n(gamma)) rounds, for any arbitrarily small constant gamma > 0. Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate CONGESTED-CLIQUE algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC'17] Finally, we deal with inter-cluster edges using recursive calls.
graph embedding is a crucial method to produce node features that can be used for various machine learning tasks. Because of the large number of embedded parameters in large graphs, a single machine cannot load the en...
详细信息
ISBN:
(纸本)9783030821364;9783030821357
graph embedding is a crucial method to produce node features that can be used for various machine learning tasks. Because of the large number of embedded parameters in large graphs, a single machine cannot load the entire graph into GPUs at once, so a partitioning strategy is required. However, there are some problems with partitioning strategies. Firstly, partitioning introduces data I/O and processing overhead, which increases training time, especially on the cluster with a small number of sites. Secondly, partitioning can affect the performance of the model. For multi-relation graphs, this effect is often negative. To address these problems, we propose the training pipeline and random partitions recombination methods. The training pipeline can reduce the time overhead by masking data loading time to GPU computation, and partitions recombination can effectively improve multi-relation model performance. We conducted experiments on multi-relation graphs and social networks, and the results show that both methods are effective.
We prove that any n-node graph G with diameter D admits shortcuts with congestion O(delta D log n) and dilation O(delta D), where delta is the maximum edge-density of any minor of G. Our proof is simple and constructi...
详细信息
ISBN:
(纸本)9781450385480
We prove that any n-node graph G with diameter D admits shortcuts with congestion O(delta D log n) and dilation O(delta D), where delta is the maximum edge-density of any minor of G. Our proof is simple and constructive with a (Theta) over tilde(delta D)-round(1) distributed construction algorithm. Our results are tight up to logarithmic factors and generalize, simplify, unify, and strengthen several prior results. For example, for graphs excluding a fixed minor, i.e., graphs with constant delta, only (O) over tilde (D-2) bound was known based on a very technical proof that relies on the Robertson-Seymour graph Structure Theorem. A direct consequence of our result is this: many graph families, including any minor-excluded ones, have near-optimal (Theta) over tilde (D)-round distributedalgorithms for many fundamental communication primitives and optimization problems in the standard synchronous message-passing model with logarithmic message sizes, i.e., the CONGEST model. These problems include minimum spanning tree, minimum cut approximation, and shortest-path approximations.
暂无评论