Abstract In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n -node graphs. For every integer $$k \ge 1$$ , O (1)-round algorithms for constructing O ( k )-spanners with $$O(n^{1+1/k})$$ edges in unweighted graphs, and O ( k )-spanners with $$O(n^{1+1/k} \log {n})$$ edges in weighted graphs. An O (1)-round algorithm for $$O(\log {n})$$ -approximation for APSP in unweighted graphs. An O (1)-round algorithm for $$O(\log ^2{n})$$ -approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O ( k )-spanners in this model require $${{\,\textrm{poly}\,}}(\log {k})$$ rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require $${{\,\textrm{poly}\,}}(\log {\log {n}})$$ rounds [Dory, Parter, PODC ’20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O (1)-round algorithms for spanners and approximate shortest paths in this model as well.

The recent advent of programmable switches makes distributed algorithms readily deployable in real-world datacenter networks. However, there are still gaps between theory and practice that prevent the smooth adaptation of CONGEST algorithms to these environments. In this paper, we focus on the memory restrictions that arise in real-world deployments. We introduce the μ-CONGEST model where on top of the bandwidth restriction, the memory of nodes is also limited to μ words, in line with real-world systems. We provide fast algorithms of two main flavors.

In this paper, we present new algorithms for approximating All-Pairs Shortest Paths (APSP) in the Congested Clique model. We present randomized algorithms for weighted undirected graphs.

In most modern networks, nodes have access to various modes of communication each with different characteristics. In this work we consider the Hybrid model of distributed computing, introduced recently by Augustine, Hinnenthal, Kuhn, Scheideler, and Schneider (SODA 2020), where nodes have access to two different communication modes: high-bandwidth local communication along the edges of the graph and low-bandwidth all-to-all communication, capturing the non-uniform nature of modern communication networks. It is noteworthy that the Hybrid model in its most general form covers most of the classical distributed models as marginal cases.

We revisit the classic broadcast problem, wherein we have k messages, each composed of O(log n) bits, distributed arbitrarily across a network. The objective is to broadcast these messages to all nodes in the network. In the distributed CONGEST model, a textbook algorithm solves this problem in O(D+k) rounds, where D is the diameter of the graph. While the O(D) term in the round complexity is unavoidable---given that Ω(D) rounds are necessary to solve broadcast in any graph ---it remains unclear whether the O(k) term is needed in all graphs. In cases where the minimum cut size is one, simply transmitting messages from one side of the cut to the other would require Ω(k) rounds. However, if the size of the minimum cut is larger, it may be possible to develop faster algorithms. This motivates the exploration of the broadcast problem in networks with high edge connectivity.

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 open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size p in $$n^{1 - 2/p + o(1)}$$ rounds in the Congest model. For triangles, our $$n^{1/3+o(1)}$$ round complexity improves upon the previous state of the art of $$n^{2/3+o(1)}$$ rounds (Chang and Saranurak, in: 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pp 377–388. IEEE Computer Society, Los Alamito, 2020. https://doi.org/10.1109/FOCS46700.2020.00043 ). For cliques of size $$p \ge 4$$ , ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values $$p \ge 3$$ our algorithms are tight up to an $$n^{o(1)}$$ subpolynomial factor, which comes from the deterministic routing procedure we use.

In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed CONGESTED CLIQUE model. Specifically, we show the following results for undirected n-node graphs. ulFor every integer k ≥ 1, O(1)-round algorithms for constructing O(k)-spanners with O(n1+1/k) edges in unweighted graphs, and O(k)-spanners with O(n1+1/k log n) edges in weighted graphs. An O(1)-round algorithm for O(log n)-approximation for APSP in unweighted graphs. An O(1)-round algorithm for O(log2n)-approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O(k)-spanners in this model require poly(log k) rounds [Parter, Yogev, DISC '18] [Biswas et al., SPAA '21], and the fastest algorithms for approximate shortest paths require poly(log log n) rounds [Dory, Parter, PODC '20]. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O(1)-round algorithms for spanners and approximate shortest paths in this model as well.

We extract a core principle that underlies seemingly different fundamental distributed settings, which is that sparsity awareness may induce faster algorithms for core problems in these settings. To leverage this, we establish a new framework by developing an intermediate auxiliary model which is weak enough to be successfully simulated in the classic congest model given low mixing time, as well as in the recently introduced hybrid model. We prove that despite imposing harsh restrictions, this artificial model allows balancing massive data transfers with a maximal utilization of bandwidth. We then exemplify the power we gain from our methods, by deriving fast shortest-paths algorithms which greatly improve upon the state-of-the-art.

The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from Õ(n^{1/3}) sources which completes in Õ(n^{1/3}) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC ’20], which computes shortest paths from a single source in Õ(n^{2/5}) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1+ε)-approximation for unweighted diameter, both in Õ(n^{1/3}) rounds w.h.p., which is comparable to the ̃ Ω(n^{1/3}) lower bound of [Kuhn and Schneider, PODC ’20] for a (2-ε)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities.

Abstract We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A $$(2+\epsilon )$$ ( 2 + ϵ ) -approximation for all-pairs shortest paths in $$O(\log ^2{n} / \epsilon )$$ O ( log 2 n / ϵ ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A $$(1+\epsilon )$$ ( 1 + ϵ ) -approximation for multi-source shortest paths from $$O(\sqrt{n})$$ O ( n ) sources in $$O(\log ^2{n} / \epsilon )$$ O ( log 2 n / ϵ ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in $$\tilde{O}(n^{1/6})$$ O ~ ( n 1 / 6 ) rounds.

We show an Õ(np/(p+2))-round algorithm in the CONGEST model for listing of Kp (a clique with p nodes), for all p = 4, p ≥ 6. For p = 5, we show an Õ(n3/4)-round algorithm.

In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.

We show how to multiply two n×n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O(log⁡n)-bit messages, within O(nz(S)1/3nz(T)1/3/n+1) rounds of communication, where nz(S) and nz(T) denote the number of non-zero elements in S and T, respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al. (2015) [9]], and thus improves upon the state-of-the-art for matrices with o(n2) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. Our algorithmic contribution is a new deterministic method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O(m/n5/3+1) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al. (2018) [26]], and that matches the known lower bound of Ω˜(n1/3) when m=n2 of [Izumi and Le Gall (2017) [19], Pandurangan et al. (2018) [26]]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity of O(m/n5/3+1) rounds, which is (possibly more than) a cubic improvement over the previously known deterministic O(m2/n3)-round algorithm [Dolev et al. (2012) [12]].

This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing tildeΩmega (n2) lower bounds for cornerstone problems, such as minimum dominating set (MDS), Hamiltonian path, Steiner tree and max-cut. These are almost tight, since all of these problems can be solved optimally in O(n2) rounds. Moreover, we show that even in bounded-degree graphs and even in simple graphs with maximum degree 5 and logarithmic diameter, it holds that various tasks, such as finding a maximum independent set (MaxIS) or a minimum vertex cover, are still difficult, requiring a near-tight number of tildeΩ (n) rounds.

Timebanking is a growing type of peer-to-peer service exchange, but is hampered by the effort of finding good transaction partners. We seek to reduce this effort by using a Matching Algorithm for Service Transactions (MAST). MAST matches transaction partners in terms of similarity of interests and complementarity of abilities and needs. We present an experiment involving data and participants from a real timebanking network, that evaluates the acceptability of MAST, and shows that such an algorithm can retrieve matches that are subjectively better than matches based on matching the category of people's historical offers or requests to the category of a current transaction request.