This paper investigates the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover. We present randomized distributed algorithms that, while having round complexity almost matching the respective state of the art, achieve nearly exponentially smaller energy complexity. That is, in each of these algorithms, each node is awake for only an exponentially small fraction of the time, and the round complexity still remains almost the same as the best-known algorithm. During the rest of the rounds, the node does not perform any computation or communication (and any messages sent to it at that time go unheard).

We present a randomized algorithm that computes a constant approximation of a graph’s arboricity, using $\tilde O(n/\lambda )$ queries to adjacency lists and in the same time bound. Here, n and λ denote the number of nodes and the graph’s arboricity, respectively. The $\tilde O(n/\lambda )$ query complexity of our algorithm is nearly optimal. Our constant approximation settles a question of Eden, Mossel, and Ron [SODA’22], who achieved an O(log2n) approximation with the same query and time complexity and asked whether a better approximation can be achieved using near-optimal query complexity.A key technical challenge in the problem is due to recursive algorithms based on probabilistic samplings, each with a non-negligible error probability. In our case, many of the recursions invoked could have bad probabilistic samples and result in high query complexities. The particular difficulty is that those bad recursions are not easy or cheap to detect and discard. Our approach runs multiple recursions in parallel, to attenuate the error probability, using a careful scheduling mechanism that manages the speed at which each of them progresses and makes our overall query complexity competitive with the single good recursion. We find this usage of parallelism and scheduling in a sublinear algorithm remarkable, and we are hopeful that similar ideas may find applications in a wider range of sublinear algorithms that rely on probabilistic recursions.

Derandomization is one of the classic topics studied in the theory of parallel computations, dating back to the early 1980s. Despite much work, all known techniques lead to deterministic algorithms that are not work-efficient. For instance, for the well-studied problem of maximal independent set-e.g., [Karp, Wigderson STOC’84; Luby STOC’ 85; Luby FOCS’88]-state-of-theart deterministic algorithms require at least $m \cdot \operatorname{poly}(\log n)$ work, where m and n denote the number of edges and vertices. Hence, these deterministic algorithms will remain slower than their trivial sequential counterparts unless we have at least poly $(\log n)$ processors. In this paper, we present a generic parallel derandomization technique that moves exponentially closer to work-efficiency. The method iteratively rounds fractional solutions representing the randomized assignments to integral solutions that provide deterministic assignments, while maintaining certain linear or quadratic objective functions, and in an essentially work-efficient manner. As example end-results, we use this technique to obtain deterministic algorithms with $m \cdot \operatorname{poly}(\log \log n)$ work and poly $(\log n)$ depth for problems such as maximal independent set, maximal matching, and hitting set.

By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in $o(\log n)$ rounds, we can speed it up to $O(\log^*n)$ rounds, and if we have a randomized $O(\log^*n)$ rounds algorithm, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity $Θ(\log\log n)$ and deterministic complexity $Θ(\log n)$. However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem $Π$ such that the round complexity of $Π$ is $Ω(\sqrt n)$ in the usual randomized \local model with private randomness, but if the nodes have access to a source of shared randomness, then the complexity drops to $O(\log n)$. As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem $Π$ demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem $Π$ also gives a separation between finitely dependent distributions and non-signaling distributions.

The $k$-center problem is a fundamental optimization problem with numerous applications in machine learning, data analysis, data mining, and communication networks. The $k$-center problem has been extensively studied in the classical sequential setting for several decades, and more recently there have been some efforts in understanding the problem in parallel computing, on the Massively Parallel Computation (MPC) model. For now, we have a good understanding of $k$-center in the case where each local MPC machine has sufficient local memory to store some representatives from each cluster, that is, when one has $Ω(k)$ local memory per machine. While this setting covers the case of small values of $k$, for a large number of clusters these algorithms require undesirably large local memory, making them poorly scalable. The case of large $k$ has been considered only recently for the fully scalable low-local-memory MPC model for the Euclidean instances of the $k$-center problem. However, the earlier works have been considering only the constant dimensional Euclidean space, required a super-constant number of rounds, and produced only $k(1+o(1))$ centers whose cost is a super-constant approximation of $k$-center. In this work, we significantly improve upon the earlier results for the $k$-center problem for the fully scalable low-local-memory MPC model. In the low dimensional Euclidean case in $\mathbb{R}^d$, we present the first constant-round fully scalable MPC algorithm for $(2+\varepsilon)$-approximation. We push the ratio further to $(1 + \varepsilon)$-approximation albeit using slightly more $(1 + \varepsilon)k$ centers. All these results naturally extends to slightly super-constant values of $d$. In the high-dimensional regime, we provide the first fully scalable MPC algorithm that in a constant number of rounds achieves an $O(\log n/ \log \log n)$-approximation for $k$-center.

This paper presents massively parallel computation (MPC) algorithms in the strongly sublinear memory regime (aka, scalable MPC) for orienting and coloring graphs as a function of its subgraph density. Our algorithms run in poly(log log n) rounds and compute an orientation of the edges with maximum outdegree O (α log log n) as well as a coloring of the vertices with O (α log log n) colors. Here, α denotes the density of the densest subgraph. Our algorithm's round complexity is notable because it breaks the [EQUATION] barrier, which applied to the previously best known density-dependent orientation algorithm [Ghaffari, Lattanzi, and Mitrovic ICML'19] and is common to many other scalable MPC algorithms.

This paper extends and generalizes the well-known cut-matching game framework and provides a novel cut-strategy that produces constant-hop expanders.

We present the first parallel batch-dynamic algorithm for approximating coreness decomposition with worst-case update times. Given any batch of edge insertions and deletions, our algorithm processes all these updates in poly(log n) depth, using a worst-case work bound of b. poly(log n) where b denotes the batch size. This means the batch gets processed in Õ(b/p) time, given p processors, which is optimal up to logarithmic factors. Previously, an algorithm with similar guarantees was known by the celebrated work of Liu, Shi, Yu, Dhulipala, and Shun [SPAA'22], but with the caveat of the work bound, and thus the runtime, being only amortized.

This paper presents the first parallel batch-dynamic algorithms for computing spanners and sparsifiers. Our algorithms process any batch of edge insertions and deletions in an n-node undirected graph, in poly(log n) depth and using amortized work near-linear in the batch size. Our concrete results are as follows:

We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding techniques [Ghaffari, Kuhn FOCS’21; Harris FOCS’19; Fischer, Ghaffari, Kuhn FOCS’17; Fischer DISC’17] to obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local graph problems, including maximal independent set (MIS), maximum-weight independent set approximation, and minimum-cost set cover approximation. As highlights, we, in particular, obtain the following results. — We obtain a deterministic \(O(\log^{2}\Delta\cdot\log n)\) -round algorithm for computing an MIS in the \(\mathsf{LOCAL}\) model and an almost as efficient \(O(\log^{2}\Delta\cdot\log\log\Delta\cdot\log n)\) -round deterministic MIS algorithm in the \(\mathsf{CONGEST}\) model. As a result, the best known deterministic distributed time complexity of the four most widely studied distributed symmetry breaking problems (MIS, maximal matching, \((\Delta+1)\) -vertex coloring, and \((2\Delta-1)\) -edge coloring) is now \(O(\log^{2}\Delta\cdot\log n)\) . Our new MIS algorithm is also the first direct polylogarithmic-time deterministic distributed MIS algorithm, which is not based on network decomposition. — We obtain efficient deterministic distributed algorithms for rounding fractional solutions for maximum (weighted) independent set and minimum (weighted) set cover. In particular, for any constant \(\varepsilon > 0\) , we give a deterministic \(O(\log^{2}\Delta+\log^{*}n)\) -round algorithm for computing an independent set of size \((1/2-\varepsilon)\,{\cdot}\,n/\deg_{\mathrm{avg}}\) , and we give deterministic \(O(\log^{2}(\Delta W)+\log^{*}n)\) -round algorithms for computing a \((1-\varepsilon)/\Delta\) -approximation of maximum weight independent set, and for computing a \((1-\varepsilon)/r\) -approximation of maximum weight matching in hypergraphs of rank \( r \) . For minimum set cover instances with sets of size at most \( s \) and where each element is contained in at most \( t \) sets, we show that an \(O(\log s)\) -approximation can be computed in time \(O(\log s\cdot\log^{2}t+\log^{*}n)\) .

This paper improves and in two cases nearly settles, up to logarithmically lower order factors, the deterministic complexity of some of the most central problems in distributed graph algorithms, which have been studied for over three decades: • Near-Optimal Network Decomposition: We present a deterministic distributed algorithm that computes a network decomposition in$\tilde{O}(\log^{2}n)$rounds with$O(\log n)$diameter and$O(\log n)$colors. This round complexity is near-optimal in the following sense: even given an ideal network decomposition, using it (in the standard way) requires round complexity equal to the product of diameter and number of colors, and that is known to be$\tilde \Omega(\log^{2}n)$. We find this near-optimality remarkable, considering the rarity of optimal deterministic distributed algorithms and that for network decomposition, even the first polylogarithmic round algorithm was achieved only recently, by Rozhon and Ghaffari [STOC 2020], after three decades. • Near-Optimal Ruling Set: We present a deterministic distributed algorithm that computes an O(log log n) ruling set—i.e., an independent set such that each node is within its O(log log n) distance—in O(log n) rounds. This is an exponential improvement on the O(log n) ruling set of Awerbuch, Goldberg, Luby, and Plotkin [FOCS'89], while almost matching their O(log n) round complexity. Our result's round complexity nearly matches the (log n) lower bound of Balliu, Brandt, Kuhn, and Olivetti [STOC 2022] that holds for any poly(log log n) ruling set. • Improved Maximal Independent Set (MIS): We present a deterministic distributed algorithm for computing an MIS in$\tilde{O}(\log^{5/3}n)$rounds. This improves on the$\tilde{O}(\log^{2}n)$complexity achieved by Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary for any method based on network decomposition. By known reductions, the$\tilde{O}(\log^{5/3}n)$round complexity also applies to deterministic algorithms for maximal matching,$\Delta+1$vertex coloring, and$(2\Delta-1)$edge coloring. Also, via the shattering technique, the improvement spreads also to randomized complexities of these problems, e.g., the new state-of-the-art randomized complexity of$\Delta+1$vertex coloring is now$\tilde{O}$((log log$N$)5/3).

We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in Õ(n) rounds and each node is awake during only poly(log n) rounds. When a node is not awake, it performs no computations or communications and spends no energy.

The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA’19] shows that to compute a Δ + 1 coloring of the graph, where Δ denotes the maximum degree, it suffices if each node limits its color choice to O(log n) independently sampled colors in {1, 2,…, Δ + 1}. They showed that it is possible to color the resulting sparsified graph—the spanning subgraph with edges between neighbors that sampled a common color, which are only Õ(n) edges—and obtain a Δ + 1 coloring for the original graph. However, to compute the actual coloring, that information must be gathered at a single location for centralized processing. We seek instead a local algorithm to compute such a coloring in the sparsified graph. The question is if this can be achieved in poly (log n) distributed rounds with small messages.

We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in poly(łog n) depth and using poly(łog n) amortized work per update. That is, the amortized work for processing a batch of k updates is k poly(łog n), while all this work is done in poly(łog n) depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10; Baswana, Gupta, and Sen FOCS'11; and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank r---where each hyperedge has at most r endpoints---with a poly(r) increase in work, while retaining the poly(łog n) depth.

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.

A recent work by Christiansen, Nowicki, and Rotenberg [STOC’23] provides dynamic algorithms for coloring sparse graphs, concretely as a function of the graph’s arboricity α. They give two randomized algorithms: O(α logα) implicit coloring in poly(logn) worst-case update and query times, and O(min{α logα, α logloglogn}) implicit coloring in poly(logn) amortized update and query times (against an oblivious adversary). We improve these results in terms of the number of colors and the time guarantee: First, we present an extremely simple algorithm that computes an O(α)-implicit coloring with poly(logn) amortized update and query times. Second, and as the main technical contribution of our work, we show that the time complexity guarantee can be strengthened from amortized to worst-case. That is, we give a dynamic algorithm for implicit O(α)-coloring with poly(logn) worst-case update and query times (against an oblivious adversary).

In this paper, we present an efficient parallel derandomization method for randomized algorithms that rely on concentrations such as the Chernoff bound. This settles a classic problem in parallel derandomization, which dates back to the 1980s. Concretely, consider the set balancing problem where m sets of size at most s are given in a ground set of size n, and we should partition the ground set into two parts such that each set is split evenly up to a small additive (discrepancy) bound. A random partition achieves a discrepancy of O(√s logm) in each set, by Chernoff bound. We give a deterministic parallel algorithm that matches this bound, using near-linear work Õ(m+n+∑i=1m |Si|) and polylogarithmic depth poly(log(mn)). The previous results were weaker in discrepancy and/or work bounds: Motwani, Naor, and Naor [FOCS’89] and Berger and Rompel [FOCS’89] achieve discrepancy s · O(√s logm) with work Õ(m+n+∑i=1m |Si|) · mΘ(1/) and polylogarithmic depth; the discrepancy was optimized to O(√s logm) in later work, e.g. by Harris [Algorithmica’19], but the work bound remained prohibitively high at Õ(m4n3). Notice that these would require a large polynomial number of processors to even match the near-linear runtime of the sequential algorithm. Ghaffari, Grunau, and Rozhon [FOCS’23] achieve discrepancy s/poly(log(nm)) + O(√s logm) with near-linear work and polylogarithmic-depth. Notice that this discrepancy is nearly quadratically larger than the desired bound and barely sublinear with respect to the trivial bound of s. Our method is different from prior work. It can be viewed as a novel bootstrapping mechanism that uses crude partitioning algorithms as a subroutine and sharpens their discrepancy to the optimal bound. In particular, we solve the problem recursively, by using the crude partition in each iteration to split the variables into many smaller parts, and then we find a constraint for the variables in each part such that we reduce the overall number of variables in the problem. The scheme relies crucially on an interesting application of the multiplicative weights update method to control the variance losses in each iteration. Our result applies to the much more general lattice approximation problem, thus providing an efficient parallel derandomization of the randomized rounding scheme for linear programs.

A celebrated and widely used result of Lenzen and Wattenhofer [STOC’11, PODC’13] shows a constant-round (deterministic) distributed routing algorithm for the complete-graph network: if each node is the source or destination of at most Θ(n) packets, there is a constant-round deterministic distributed algorithm that routes all packets to their destinations in a constant number of rounds, on the complete-graph network. We study generalizations of this result to arbitrary network graphs and show a necessary and sufficient condition for the network so that it can route any such demand in constant rounds distributedly. One can easily see that just for the existence of a constant-round routing for all such demands, it is necessary that any cut’s size, when normalized by the number of possible edges in that cut, should be lower bounded by a positive constant. That is, for any partition of nodes with exactly k∈ [1, n/2] nodes on one side, the cut should have at least Θ(kn) edges. We call this a graph with a positive minimum normalized cut, or a positive graph for short. We show that this necessary condition is also sufficient. In particular, by tightening the Leighton-Rao multicommodity max-flow min-cut theorem for positive graphs, we show the existence of a constant-round routing in positive graphs (assuming the network graph is known globally). Then, as the main technical contribution of this paper, we also show that there is a (deterministic) distributed algorithm that computes such a constant-round routing in constant rounds in these graphs. This result allows us to vastly relax the conditions of the well-studied congested clique model of distributed computing: Any distributed algorithm for the congested clique model can be run in any positive graph network, without any asymptotic slow-down. Our results are in fact more general and they give a distributed routing bound for any network, as a function of its minimum normalized cut size (and without assuming it is a constant), within a polynomial of the relevant lower bound.

Abstract We describe a simple deterministic $$O( \varepsilon ^{-1} \log \Delta )$$ O ( ε - 1 log Δ ) round distributed algorithm for $$(2\alpha +1)(1 + \varepsilon )$$ ( 2 α + 1 ) ( 1 + ε ) approximation of minimum weighted dominating set on graphs with arboricity at most $$\alpha $$ α . Here $$\Delta $$ Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $$O(\alpha ^2)$$ O ( α 2 ) approximation in $$O(\log n)$$ O ( log n ) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha \log \Delta )$$ O ( α log Δ ) approximation in $$O(\log \Delta )$$ O ( log Δ ) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha )$$ O ( α ) approximation in $$O(\log ^2 \Delta )$$ O ( log 2 Δ ) rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized $$O(\alpha )$$ O ( α ) approximation in $$O(\alpha \log n)$$ O ( α log n ) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized $$O(\alpha \log \Delta )$$ O ( α log Δ ) round distributed algorithm that sharpens the approximation factor to $$\alpha (1+o(1))$$ α ( 1 + o ( 1 ) ) . If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve $$\alpha - 1 - \varepsilon $$ α - 1 - ε approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017).

Abstract. We study the problem of approximating the distances in an undirected weighted graph [Formula: see text] by the distances in trees based on the notion of stretch. Focusing on decentralized models of computation such as the [Formula: see text], [Formula: see text], and semi-streaming models, our main results are as follows: (1) We develop a simple randomized algorithm that constructs a spanning tree such that the expected stretch of every edge is [Formula: see text], where [Formula: see text] is the number of nodes in [Formula: see text]. If [Formula: see text] is unweighted, then this algorithm can be implemented to run in [Formula: see text] rounds in the [Formula: see text] model, where [Formula: see text] is the hop-diameter of [Formula: see text]; thus our algorithm is asymptotically optimal in this case. In the weighted case, the run-time of the algorithm matches the currently best known bound for exact single source shortest path (SSSP) computations, which despite recent progress is still separated from the lower bound of [Formula: see text] by polynomial factors. A naive attempt to replace exact SSSP computations with approximate ones in order to improve the complexity in the weighted case encounters a fundamental challenge, as the underlying decomposition technique fails to work under distance approximation. (2) We overcome this obstacle by developing a technique termed blurry ball growing. This technique, in combination with a clever algorithmic idea of Miller, Peng, and Xu (SPAA 2013), allows us to obtain low diameter graph decompositions with small edge cutting probabilities based solely on approximate SSSP computations. (3) Using these decompositions, we in turn obtain metric tree embedding algorithms in the vein of the celebrated work of Bartal (FOCS 1996), whose computational complexity is optimal up to polylogarithmic factors not only in the [Formula: see text] model but also in the [Formula: see text] and semi-streaming models. Our embeddings have the additional useful property that the tree can be mapped back to the original graph such that each edge is “used” only logarithmically many times. This property is of interest for capacitated problems and for simulating [Formula: see text] algorithms on the tree into which the graph is embedded.

We present a novel technique for work-efficient parallel derandomization, for algorithms that rely on the concentration of measure bounds such as Chernoff, Hoeffding, and Bernstein inequalities. Our method increases the algorithm’s computational work and depth by only polylogarithmic factors. Before our work, the only known method to obtain parallel derandomization with such strong concentrations was by the results of [Motwani, Naor, and Naor FOCS’89; Berger and Rompel FOCS’89], which perform a binary search in a k-wise independent space for $k=\operatorname{poly}(\log n)$. However, that method blows up the computational work by a high poly $(n)$ factor and does not yield work-efficient parallel algorithms. Their method was an extension of the approach of [Luby FOCS’88], which gave a work-efficient derandomization but was limited to algorithms analyzed with only pairwise independence. Pushing the method from pairwise to the higher k-wise analysis resulted in the $\operatorname{poly}(n)$ factor computational work blow-up. Our work can be viewed as an alternative extension from the pairwise case, which yields the desired strong concentrations while retaining work efficiency up to logarithmic factors. Our approach works by casting the problem of determining the random variables as an iterative process with poly $(\log n)$ iterations, where different iterations have independent randomness. This is done so that for the desired concentrations, we need only pairwise independence inside each iteration. In particular, we model each binary random variable as a result of a gradual random walk, and our method shows that the desired Chernoff-like concentrations about the endpoints of these walks can be boiled down to some pairwise analysis on the steps of these random walks in each iteration (while having independence across iterations). Hence, we can fix the randomness of each iteration efficiently before proceeding to the next.

We present randomized distributed algorithms for the maximal independent set problem (MIS) that, while keeping the time complexity nearly matching the best known, reduce the energy complexity substantially. These algorithms work in the standard CONGEST model of distributed message passing with O(log n) bit messages. The time complexity measures the number of rounds in the algorithm. The energy complexity measures the number of rounds each node is awake; during other rounds, the node sleeps and cannot perform any computation or communications.

We provide the first deterministic distributed synchronizer with near-optimal time complexity and message complexity overheads. Concretely, given any distributed algorithm A that has time complexity T and message complexity M in the synchronous message-passing model (subject to some care in defining the model), the synchronizer provides a distributed algorithm A′ that runs in the asynchronous message-passing model with time complexity T · poly(log n) and message complexity (M + m) · poly(log n). Here, n and m denote the number of nodes and edges in the network, respectively. The synchronizer is deterministic in the sense that if algorithm A is deterministic, then so is algorithm A′. Previously, only a randomized synchronizer with near-optimal overheads was known by seminal results of Awerbuch, Patt-Shamir, Peleg, and Saks [STOC 1992] and Awerbuch and Peleg [FOCS 1990]. We also point out and fix some inaccuracies in these prior works.

This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the main ingredient in these results, we develop novel randomized distributed algorithms that we can analyze using only pairwise independence, and we can thus derandomize efficiently. As our most prominent end-result, we obtain a deterministic construction for O(log n)-color O(log n · log log log n)- strong diameter network decomposition in Õ(log3 n) rounds. This is the first construction that achieves almost log n in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions [Rozhoň, Ghaffari STOC'20; Ghaffari, Grunau, Rozhoň SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozhoň, Grunau FOCS'22].

The minimum-cost k-edge-connected spanning subgraph (k-ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While the round complexity of distributedly computing the latter has been well-understood, the former remains mostly open, especially as soon as k ≥ 3. In this paper, we present the first distributed algorithm that computes an approximation of k-ECSS in sublinear time for general k. Concretely, we describe a randomized distributed algorithm that, in rounds, computes a k-edge-connected spanning subgraph whose cost is within an O(log n log k) factor of optimal. Here, n and D denote the number of vertices and diameter of the graph, respectively. This time complexity is nearly optimal for any k = poly(log n), almost matching an lower bound. Our algorithm is the first to achieve a sublinear round complexity for k ≥ 3. We note that this case is considerably more challenging than the well-studied and well-understood k =1 case—better known as MST—and the closely related k = 2 case. Our algorithm is based on reducing the k-ECSS problem to k set cover instances, in which we gradually augment the connectivity of the spanning subgraph. To solve each set cover instance, we combine new structural observations on minimum cuts with graph sketching ideas. One key ingredient in our algorithm is a novel structural lemma that allows us to compress the information about all minimum cuts in a graph into a succinct representation, which is computed in a decentralized fashion. We hope that this succinct representation may find applications in other computational settings or for other problems.

We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding techniques [Ghaffari, Kuhn FOCS'21; Harris FOCS'19; Fischer, Ghaffari, Kuhn FOCS'17; Fischer DISC'17] to obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local graph problems, including maximal independent set (MIS), maximum-weight independent set approximation, and minimum-cost set cover approximation. As highlights, we in particular obtain the following results.

We present an O(log3 log n)-round distributed algorithm for the (Δ + 1)-coloring problem, where each node broadcasts only one O(log n)-bit message per round to its neighbors. Previously, the best such broadcast-based algorithm required O(log n) rounds. If Δ ∈ Ω(log 3 n), our algorithm runs in O(log* n) rounds. Our algorithm's round complexity matches the state-of-the-art in the much more powerful CONGEST model [Halldórsson et al., STOC'21 & PODC'22], where each node sends one different message to each of its neighbors, thus sending up to Θ(n log n) bits per round. This is the best complexity known, even if message sizes are unbounded.

We present an Õ(log2 n) round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, Δ+1 vertex coloring, and 2Δ−1 edge coloring. These four problems are among the most central problems in distributed graph algorithms and have been studied extensively for the past four decades. This improved round complexity comes closer to the Ω(logn) lower bound of maximal independent set and maximal matching [Balliu et al. FOCS ’19]. The previous best known deterministic complexity for all of these problems was Θ(log3 n). Via the shattering technique, the improvement permeates also to the corresponding randomized complexities, e.g., the new randomized complexity of Δ+1 vertex coloring is now Õ(log2logn) rounds.

Abstract We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $$G=(V,E)$$ G=(V,E) is the average over the times at which the nodesVofGfinish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) inn-node graphs of maximum degree $$\Delta $$ Δ is at least $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω(min{logΔloglogΔ,lognloglogn}) . This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM’16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω(min{logΔloglogΔ,lognloglogn}) —this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an $$O(\sqrt{\log \log n})$$ O(loglogn) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity toO(1). For maximal matching, we show that while the randomized node-averaged complexity is $$\Omega \big (\min \big \{\frac{\log \Delta }{\log \log \Delta },\sqrt{\frac{\log n}{\log \log n}}\big \}\big )$$ Ω(min{logΔloglogΔ,lognloglogn}) , the randomized edge-averaged complexity isO(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is $$O(\log ^2\Delta + \log ^* n)$$ O(log2Δ+log∗n) and the deterministic node-averaged complexity of maximal matching is $$O(\log ^3\Delta + \log ^* n)$$ O(log3Δ+log∗n) . Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be $$\Theta (\log n)$$ Θ(logn) , even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity $$O(\log ^* n)$$ O(log∗n) , while keeping the worst-case complexity in $$O(\log n)$$ O(logn) .

We present a randomized Local Computation Algorithm (LCA) with query complexity poly $(\Delta) \cdot \log n$ for the Maximal Independent Set (MIS) problem. That is, the algorithm determines whether each node is in the computed MIS or not using poly $(\Delta)\cdot\log n$ queries to the adjacency lists of the graph, with high probability, and this can be done for different nodes simultaneously and independently. Here $\Delta$ and n denote the maximum degree and the number of nodes. This algorithm resolves a key open problem in the study of local computations and sublinear algorithms (attributed to Rubinfeld).

We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in Õ(D + √n ) rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai [STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in Õ(D) rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family.

We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G=(V,E) is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems.

We describe a simple deterministic O(ε-1 log Δ) round distributed algorithm for (2α+ 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α. Here Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation [Kuhn, Moscibroda, and Wattenhofer JACM'16].

This paper presents an O(log log đ) round massively parallel algorithm for 1 + ε approximation of maximum weighted b-matchings, using near-linear memory per machine. Here đ denotes the average degree in the graph and ε is an arbitrarily small positive constant. Recall that b-matching is the natural and well-studied generalization of the matching problem where different vertices are allowed to have different numbers of incident edges in the matching.

Chatterjee, Gmyr, and Pandurangan [PODC 2020] recently introduced the notion of awake complexity for distributed algorithms, which measures the number of rounds in which a node is awake. In the other rounds, the node is sleeping and performs no computation or communication. Measuring the number of awake rounds can be of significance in many settings of distributed computing, e.g., in sensor networks where energy consumption is of concern. In that paper, Chatterjee et al. provide an elegant randomized algorithm for the Maximal Independent Set (MIS) problem that achieves an O(1) node-averaged awake complexity. That is, the average awake time among the nodes is O(1) rounds. However, to achieve that, the algorithm sacrifices the more standard round complexity measure from the well-known O(łog n) bound of MIS, due to Luby [STOC'85], to O(łog^3.41 n) rounds. Our first contribution is to present a simple randomized distributed MIS algorithm that, with high probability, has O(1) node-averaged awake complexity and O(łog n) worst-case round complexity. Our second, and more technical contribution, is to show algorithms with the same O(1) node-averaged awake complexity and O(łog n) worst-case round complexity for 1+ε approximation of maximum matching and 2+ε approximation of minimum vertex cover, where ε denotes an arbitrary small positive constant.

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification:We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in polylog(n) rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only n + o (n) edges in which the pairwise distances are stretched by a factor of at most O(logn · 2O(log* n) ).

This paper studies the fundamental task of establishing routing paths in distributed networks. We prove the existence of compact routing tables that store in each network-node few simple forwarding rules tracing out hop-constrained and oblivious routing paths for any pair of nodes. For any collection of pairs the congestion of these paths is almost-optimal, i.e., competitive with the globally optimal solution up to a sub-polynomial factor.

We present a simple deterministic distributed algorithm that computes a ($\Delta+1$)-vertex coloring in$O(\text{log}^{2}\Delta. \text{log}\ n)$rounds. The algorithm can be implemented with$O(\text{log}\ n)$-bit messages. The algorithm can also be extended to the more general ($degree+1$)-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for ($\Delta +1$)-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an$O(\text{log}^{5}n)$-round algorithm for ($\Delta+1$)-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for ($\Delta +1$)-coloring, now reaching the bound of$O(\text{log}^{3}\text{log}\ n)$rounds. As a further application, we provide faster deterministic distributed algorithms for the following vertex coloring variants. In graphs of arboricity$a$, we show that a$(2+\varepsilon)a$-vertex coloring can be computed in$O(\text{log}^{3}a\cdot \text{log} n)$rounds. We also show that for$\Delta\geq 3$, a$\Delta$-coloring of a$\Delta$-colorable graph$G$can be computed in$O(\text{log}^{2}\Delta\cdot \text{log}^{2}n)$rounds.

Network decomposition is a central concept in the study of distributed graph algorithms. We present the first polylogarithmic-round deterministic distributed algorithm with small messages that constructs a strong-diameter network decomposition with polylogarithmic parameters.

We prove that any n-node graph G with diameter D admits shortcuts with congestion O(δ D log n) and dilation O(δ D), where δ is the maximum edge-density of any minor of G. Our proof is simple and constructive with a tildeΘ (δ D)-round1 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 δ, only a Õ (D2) bound was known based on a very technical proof that relies on the Robertson-Seymour Graph Structure Theorem.

Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improvements in the (deterministic and randomized) complexity of several well-studied graph problems. - We provide a deterministic distributed network decomposition algorithm with O(log5 n) round complexity, using O(log n)-bit messages. This improves on the O(log7 n)-round algorithm of Rozhoň and Ghaffari [STOC'20], which used large messages, and their O(log8 n)-round algorithm with O(log n)-bit messages. This directly leads to similar improvements for a wide range of deterministic and randomized distributed algorithms, whose solution relies on network decomposition, including the general distributed derandomization of Ghaffari, Kuhn, and Harris [FOCS'18]. - One drawback of the algorithm of Rozhoň and Ghaffari, in the CONGEST model, was its dependence on the length of the identifiers. Because of this, for instance, the algorithm could not be used in the shattering framework in the CONGEST model. Thus, the state of the art randomized complexity of several problems in this model remained with an additive term, which was a clear leftover of the older network decomposition complexity [Panconesi and Srinivasan STOC'92]. We present a modified version that remedies this, constructing a decomposition whose quality does not depend on the identifiers, and thus improves the randomized round complexity for various problems.

We present a randomized parallel algorithm, in the Exclusive-Read Exclusive-Write (EREW) PRAM model, that computes a Maximal Independent Set (MIS) in O(log n) time and using O(m log2 n) work, with high probability. Thus, MIS ∊ RNC1. This time complexity is optimal and it improves on the celebrated O(log2 n) time algorithms of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86], which had remained the state of the art for the past 35 years.

Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms---usually sublogarithmic-time and often poly(łogłog n)-time, or even faster---for a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widely-adopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an all-to-all manner to process large-scale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )-spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmic-time MPC algorithms for spanner construction.

We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing.

Abstract We present a randomized distributed algorithm that computes a $$\Delta $$ Δ -coloring in any non-complete graph with maximum degree $$\Delta \ge 4$$ Δ ≥ 4 in $$O(\log \Delta ) + 2^{O(\sqrt{\log \log n})}$$ O ( log Δ ) + 2 O ( log log n ) rounds, as well as a randomized algorithm that computes a $$\Delta $$ Δ -coloring in $$O((\log \log n)^2)$$ O ( ( log log n ) 2 ) rounds when $$\Delta \in [3, O(1)]$$ Δ ∈ [ 3 , O ( 1 ) ] . Both these algorithms improve on an $$O(\log ^3 n / \log \Delta )$$ O ( log 3 n / log Δ ) -round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $$\Omega (\log \log n)$$ Ω ( log log n ) round lower bound of Brandt et al. (STOC’16).

We present two Massively Parallel Computation (MPC) algorithms for the Minimum Cut problem: an O(1)-round exact algorithm with Õ(n) memory per machine, and an O(log n · log log n) round (2 + ε) approximation with Õ(nα) memory per machine, for any positive constant α < 1. Both algorithms use Õ(m) global memory.

We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. We demonstrate the power of our new approach by obtaining better algorithms for sequential, distributed, and parallel models of computation. Our end results include the following randomized algorithms for computing edge connectivity, with high probability1: Two sequential algorithms with complexities O(m log n) and O(m + n log3 n). These improve on a long line of developments including a celebrated O(m log3 n) algorithm of Karger [STOC'96] and the state of the art O(m log2 n(log log n)2) algorithm of Henzinger et al. [SODA'17]. Moreover, our O(m + n log3 n) algorithm is optimal when m = Ω (n log3 n). An round distributed algorithm, where D denotes the graph diameter. This improves substantially on a recent breakthrough of Daga et al.[STOC'19], which achieved a round complexity of , hence providing the first sublinear distributed algorithm for exactly computing the edge connectivity. The first O(1) round algorithm for the massively parallel computation setting with linear memory per machine.

We present a massively parallel algorithm, with near-linear memory per machine, that computes a (2+ε)-approximation of minimum-weight vertex cover in O(log log d) rounds, where d is the average degree of the input graph.

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2 O(√logn)-time algorithm of Panconesi and Srinivasan [STOC’92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial’s question about the deterministic complexity of maximal independent set [FOCS’87; SICOMP’92]—which had been called the most outstanding problem in the area.

Dynamic programming is a powerful technique that is, unfortunately, often inherently sequential. That is, there exists no unified method to parallelize algorithms that use dynamic programming. In this paper, we attempt to address this issue in the Massively Parallel Computations (MPC) model which is a popular abstraction of MapReduce-like paradigms. Our main result is an algorithmic framework to adapt a large family of dynamic programs defined over trees. We introduce two classes of graph problems that admit dynamic programming solutions on trees. We refer to them as "(polylog)-expressible" and "linear-expressible" problems. We show that both classes can be parallelized in $O(\log n)$ rounds using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in $O(\log n)$ rounds of MPC, the dynamic programming solution of graph problems such as minimum bisection, $k$-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.

We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC1is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.

Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest subgraph and the $k$-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of $k$-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al. (ICML’18). Compared to the prior work on densest subgraph presented by Bahmani et al. (VLDB’12, ’14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques.

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly log n-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G=(V,E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly log n-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results:

In this paper, we present new randomized algorithms that improve the complexity of the classic (Δ+1)-coloring problem, and its generalization (Δ+1)-list-coloring, in three well-studied models of distributed, parallel, and centralized computation: Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Δ + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log* Δ)-round randomized algorithms of Parter and Su [DISC'18] and O((log log Δ)⋅ log* Δ)-round randomized algorithm of Parter [ICALP'18].

The minimum-weight 2-edge-connected spanning subgraph (2-ECSS) problem is a natural generalization of the well-studied minimum-weight spanning tree (MST) problem, and it has received considerable attention in the area of network design. The latter problem asks for a minimum-weight subgraph with an edge connectivity of 1 between each pair of vertices while the former strengthens this edge-connectivity requirement to 2. Despite this resemblance, the 2-ECSS problem is considerably more complex than MST. While MST admits a linear-time centralized exact algorithm, 2-ECSS is NP-hard and the best known centralized approximation algorithm for it (that runs in polynomial time) gives a 2-approximation.

We attempt to better understand randomization in local distributed graph algorithms by exploring how randomness is used and what we can gain from it:

Maximal Independent Set (MIS) is one of the central problems in distributed graph algorithms. The celebrated works of Luby [STOC’85] and Alon, Babai, and Itai [JALG’86] provide O(log n)-round randomized distributed MIS algorithms, which work with O(log n)-bit messages. This round complexity was improved to in a breakthrough of Barenboim, Elkin, Pettie, and Schneider [FOCS’11; JACM’16] and then to by Ghaffari [SODA’16], where Δ denotes the maximum degree. However, these improvements have one drawback: they require much larger messages, up to poly (Δ log n) bits. Indeed, the question of improving the O(log n) round complexity using small messages has remained open for three decades, for essentially all values of Δ, except for Δ = o(log n) where there are O(Δ + log* n)-round deterministic algorithms. We present a randomized distributed MIS algorithm, with O(log n)-bit messages, that achieves a round complexity of min{log Δ · , O(log Δ · log log n) + }. This is the first algorithm with small messages that improves on the O(log n) round complexity of Luby and Alon et al. for a wide range of A, and its complexity almost matches that of the best known algorithm using unbounded message sizes. As applications of this MIS algorithm or along the way to it, we obtain improved distributed algorithms with small messages for some other well-studied problems including network decompositions, (Δ + 1)-vertex coloring, and ruling sets.

We introduce a method for “sparsifying” distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic O(log n)-round parallel (PRAM) counterparts for problems such as Maximal Independent Set (MIS), Maximal Matching, 2-Approximation of Minimum Vertex Cover, and (1 + ∊)-Approximation of Maximum Matching. Currently, all such MPC algorithms require memory of per machine: Czumaj et al. [STOC'18] were the first to handle memory, running in O((log log n)2) rounds, who improved on the n1+Ω(1) memory requirement of the O(1)-round algorithm of Lattanzi et al [SPAA'11]. We obtain -round MPC algorithms for all these four problems that work even when each machine has strongly sublinear memory, e.g., nα for any constant α ∊ (0, 1). Here, Δ denotes the maximum degree. These are the first sublogarithmictime MPC algorithms for (the general case of) these problems that break the linear memory barrier. LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity ΔO(log Δ) poly(log n), by Ghaffari [SODA'16], which improved over the ΔO(log2 Δ) poly(log n) bound of Levi et al. [Algorithmica'17]. As pointed out by Rubinfeld, obtaining a query complexity of poly(Δ log n) remains a central open question. Ghaffari's bound almost reaches a barrier common to all known MIS LCAs, which sim-ulate a distributed algorithm by learning the full local topology, à la Parnas-Ron [TCS'07]. There is a barrier because the distributed complexity of MIS has a lower bound of , by results of Kuhn, et al. [JACM'16], which means this methodology cannot go below query complexity . We break this barrier and obtain an LCA for MIS that has a query complexity ΔO(log log Δ) poly(log n).

In this paper, we study distributed graph algorithms in networks in which the nodes have a limited communication capacity. Many distributed systems are built on top of an underlying networking infrastructure, for example by using a virtual communication topology known as an overlay network. Although this underlying network might allow each node to directly communicate with a large number of other nodes, the amount of communication that a node can perform in a fixed amount of time is typically much more limited. We introduce the Node-Capacitated Clique model as an abstract communication model, which allows us to study the effect of nodes having limited communication capacity on the complexity of distributed graph computations. In this model, the n nodes of a network are connected as a clique and communicate in synchronous rounds. In each round, every node can exchange messages of $O(łog n)$ bits with at most $O(łog n)$ other nodes. When solving a graph problem, the input graph G is defined on the same set of n nodes, where each node knows which other nodes are its neighbors in G. To initiate research on the Node-Capacitated Clique model, we present distributed algorithms for the Minimum Spanning Tree (MST), BFS Tree, Maximal Independent Set, Maximal Matching, and Vertex Coloring problems. We show that even with only $O(łog n)$ concurrent interactions per node, the MST problem can still be solved in polylogarithmic time. In all other cases, the runtime of our algorithms depends linearly on the arboricity of G, which is a constant for many important graph families such as planar graphs.

Given an undirected graph with integer edge lengths, we study the problem of approximating the distances in the graph by a spanning tree based on the notion of stretch. Our main contribution is a distributed algorithm in the CONGEST model of computation that constructs a random spanning tree with the guarantee that the expected stretch of every edge is O(log^{3} n), where n is the number of nodes in the graph. If the graph is unweighted, then this algorithm can be implemented to run in O(D) rounds, where D is the hop-diameter of the graph, thus being asymptotically optimal. In the weighted case, the run-time of our algorithm matches the currently best known bound for exact distance computations, i.e., O~ (min{sqrt{n D}, sqrt{n} D^{1 / 4} + n^{3 / 5} + D}). We stress that this is the first distributed construction of spanning trees leading to poly-logarithmic expected stretch with non-trivial running time.

The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithms. In this paper, we combine the method of conditional expectation with network decompositions to obtain a generic and clean recipe for derandomizing LOCAL algorithms. This leads to significant improvements on a number of problems, in cases resolving known open problems. Two main results are: - An improved deterministic distributed algorithm for hypergraph maximal matching, improving on Fischer, Ghaffari, and Kuhn [FOCS '17]. This yields improved algorithms for edge-coloring, maximum matching approximation, and low out-degree edge orientation. The last result gives the first positive resolution in the Open Problem 11.10 in the book of Barenboim and Elkin. - Improved randomized and deterministic distributed algorithms for the Lovász Local Lemma, which get closer to a conjecture of Chang and Pettie [FOCS '17].

We present O(loglog n) -round algorithms in the Massively Parallel Computation (MPC) model, with Õ (n) memory per machine, that compute a maximal independent set, a 1+ε approximation of maximum matching, and a 2+εapproximation of minimum vertex cover, for any n-vertex graph and any constant \eps>0. These improve the state of the art as follows:

We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1+o(1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(logn). For smaller Δ, we give a polylogarithmic-time 3Δ/2-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors, and they improve significantly on the recent polylogarithmic-time (2Δ−1)(1+o(1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2Δ−1)-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

Computing shortest paths is one of the central problems in the theory of distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem, culminating in an algorithm of Henzinger, Krinninger, and Nanongkai [STOC’16] which deterministically computes (1+o(1))-approximate shortest paths in Õ(D+√n) time, where D is the hop-diameter of the graph. Up to logarithmic factors, this time complexity is optimal, matching the lower bound of Elkin [STOC’04].

This paper presents a deterministic distributed algorithm for computing an f(1+epsilon) approximation of the well-studied minimum set cover problem, for any constant epsilon>0, in O(log (f Delta)/log log (f Delta)) rounds. Here, f denotes the maximum element frequency and Delta denotes the cardinality of the largest set. This f(1+epsilon) approximation almost matches the f-approximation guarantee of standard centralized primal-dual algorithms, which is known to be essentially the best possible approximation for polynomial-time computations. The round complexity almost matches the Omega(log (Delta)/log log (Delta)) lower bound of Kuhn, Moscibroda, Wattenhofer [JACM'16], which holds for even f=2 and for any poly(log Delta) approximation. Our algorithm also gives an alternative way to reproduce the time-optimal 2(1+epsilon)-approximation of vertex cover, with round complexity O(log Delta/log log Delta), as presented by Bar-Yehuda, Censor-Hillel, and Schwartzman [PODC'17] for weighted vertex cover. Our method is quite different and it can be viewed as a locality-optimal way of performing primal-dual for the more general case of set cover. We note that the vertex cover algorithm of Bar-Yehuda et al. does not extend to set cover (when f >= 3).

Sampling constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of sampling algorithms is the Markov Chain Monte Carlo method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution. Many of the traditional Markov chains, such as the Glauber dynamics, do not scale well with increasing dimension. To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions. Concretely, we present a Markov chain that mixes in O(log n) rounds when Dobrushin's condition for the Gibbs distribution is satisfied. This improves over the LubyGlauber algorithm by Feng, Sun, and Yin [PODC'17], which needs O(Delta log n) rounds, and their LocalMetropolis algorithm, which converges in O(log n) rounds but requires a considerably stronger mixing condition. Here, n denotes the number of nodes in the graphical model inducing the Gibbs distribution, and Delta its maximum degree. In particular, our method can sample a uniform proper coloring with alpha Delta colors in O(log n) rounds for any alpha >2, which almost matches the threshold of the sequential Glauber dynamics and improves on the alpha>2 + sqrt{2} threshold of Feng et al.

This paper presents improved deterministic distributed algorithms, with O(log n)-bit messages, for some basic graph problems. The common ingredient in our results is a deterministic distributed algorithm for computing a certain hitting set, which can replace the random part of a number of standard randomized distributed algorithms. This deterministic hitting set algorithm itself is derived using a simple method of conditional expectations. As one main end-result of this derandomized hitting set, we get a deterministic distributed algorithm with round complexity 2^O(sqrt{log n * log log n}) for computing a (2k-1)-spanner of size O~(n^{1+1/k}). This improves considerably on a recent algorithm of Grossman and Parter [DISC'17] which needs O(n^{1/2-1/k} * 2^k) rounds. We also get a 2^O(sqrt{log n * log log n})-round deterministic distributed algorithm for computing an O(log^2 n)-approximation of minimum dominating set; all prior algorithms for this problem were either randomized or required large messages.

We show that many classical optimization problems - such as (1 +/- epsilon)-approximate maximum flow, shortest path, and transshipment - can be computed in tau_{mix}(G)* n^o(1) rounds of distributed message passing, where tau_{mix}(G) is the mixing time of the network graph G. This extends the result of Ghaffari et al. [PODC'17], whose main result is a distributed MST algorithm in tau_{mix}(G)* 2^O(sqrt{log n log log n}) rounds in the CONGEST model, to a much wider class of optimization problems. For many practical networks of interest, e.g., peer-to-peer or overlay network structures, the mixing time tau_{mix}(G) is small, e.g., polylogarithmic. On these networks, our algorithms bypass the Omega(sqrt n+D) lower bound of Das Sarma et al. [STOC'11], which applies for worst-case graphs and applies to all of the above optimization problems. For all of the problems except MST, this is the first distributed algorithm which takes o(sqrt n) rounds on a (nontrivial) restricted class of network graphs. Towards deriving these improved distributed algorithms, our main contribution is a general transformation that simulates any work-efficient PRAM algorithm running in T parallel rounds via a distributed algorithm running in T * tau_{mix}(G)* 2^O(sqrt{log n}) rounds. Work- and time-efficient parallel algorithms for all of the aforementioned problems follow by combining the work of Sherman [FOCS'13, SODA'17] and Peng and Spielman [STOC'14]. Thus, simulating these parallel algorithms using our transformation framework produces the desired distributed algorithms. The core technical component of our transformation is the algorithmic problem of solving multi-commodity routing - that is, roughly, routing n packets each from a given source to a given destination - in random graphs. For this problem, we obtain a new algorithm running in 2^O(sqrt{log n}) rounds, improving on the 2^O(sqrt{log n log log n}) round algorithm of Ghaffari, Kuhn, and Su [PODC'17]. As a consequence, for the MST problem in particular, we obtain an improved distributed algorithm running in tau_{mix}(G)* 2^O(sqrt{log n}) rounds.

We present a near-optimal distributed algorithm for $(1+o(1))$-approximation of single-commodity maximum flow in undirected weighted networks that runs in $(D+\sqrt{n})\cdot n^{o(1)}$ communication rounds in the CONGEST model. Here, $n$ and $D$ denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial bound of $O(n^2)$, and it nearly matches the $\tilde{\Omega}(D+\sqrt{n})$-round complexity lower bound. The development of the algorithm entails two subresults of independent interest: (i) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of a spanning tree of average stretch $n^{o(1)}$. (ii) A $(D+\sqrt{n})\cdot n^{o(1)}$-round distributed construction of an $n^{o(1)}$-congestion approximator consisting of the cuts induced by $O(\log n)$ virtual trees. The distributed representation of the cut approximator allows for evaluation in $(D+\sqrt{n})\cdot n^{o(1)}$ rounds. All our algorithms make use of randomization and succeed with high probability.

We present a deterministic distributed algorithm that computes a (2Δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree Δ, in O(log8Δ·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 Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2O(√(log n)by Panconesi and Srinivasan [STOC'92] and Õ(√(Δ)) + 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Δ-1)-edge-coloring 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 Δ, this algorithm computes a maximal matching in O(r5log6+log rΔ·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 Elkins book, a ((log Δ/ε)O(log 1/ε))-round deterministic algorithm for (1+ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most ⌈(1+ε)λ⌉, for any constant ε>0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.

We present a simple distributed Δ-approximation algorithm for maximum weight independent set (MaxIS) in the CONGEST model which completes in O(MIS ⋅ log W) rounds, where Δ is the maximum degree, MIS is the number of rounds needed to compute a maximal independent set (MIS) on G, and W is the maximum weight of a node. Plugging in the best known algorithm for MIS gives a randomized solution in O(log n log W) rounds, where n is the number of nodes. We also present a deterministic O(Δ +log* n)-round algorithm based on coloring.

Computing a Maximal Independent Set (MIS) is a central problem in distributed graph algorithms. This paper presents an improved randomized distributed algorithm for 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(log n) bits to each other node. We present a randomized algorithm that computes an MIS in Õ((log Δ)/(√(log n)) + 1 ) ≤ Õ(√(log Δ)) rounds of congested clique, with high probability. Here Δ denotes the maximum degree in the graph. This improves quadratically on the O(log Δ) 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 randomized distributed algorithm that computes a minimum spanning tree in τ(G) · 2O(√(log n log log n))) rounds, in any n-node graph G with mixing time τ(G). This result provides a sub-polynomial complexity for a wide range of graphs of practical interest, and goes below the celebrated Ω(D+ √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 τ(G) · 2O(√(log n log log n)) rounds, assuming that each node v is the source or destination for at most dG(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 initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s-t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures.

We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: We present a poly log n round deterministic algorithm for (2Δ – 1)•(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ – 1) · poly log Δ-edge- coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. We show that sinkless orientation—i.e., orienting edges such that each node has at least one outgoing edge—on Δ-regular graphs can be solved in O(logA log n) rounds randomized and in O(logA n) rounds deterministically. These prove the corresponding lower bounds by Brandt et al. [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of Chang et al. for Δ-coloring Δ- regular trees. We present a randomized O (log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + ∊). This can be also turned into a decomposition into a(1 + ∊) forests when a = 0(logn) and into a(1 + ∊) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin.

This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2O(√logn). Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms.

The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy. We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for (2+o(1))Delta-edge-coloring, improving on that of Ghaffari and Su.

Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with Delta+1 colors, where Delta denotes the maximum degree. Using Delta+1 colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned. We present simple randomized distributed algorithms that, with high probability, color any n-node alpha-arboricity graph: - using (2+epsilon)alpha colors, for constant epsilon>0, in O(log n) rounds, if alpha=Omega(log n log log n), or - using O(alpha log alpha) colors, in O(log n) rounds, or - using O(alpha) colors, in O(log n min{log log n, log alpha}) rounds. These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with Theta(alpha) colors, or even poly(alpha) colors, requires Omega(log_alpha n) rounds. The previously best-known O(log n)-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses Theta(alpha^2) colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.

We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound. A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.

A fundamental result by Karger [10] states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log ( n )/λ) results in a graph that has edge connectivity Ω(λ p ), with high probability. This article proves the analogous result for vertex connectivity, when either vertices or edges are sampled. We show that for any k -vertex-connected graph G with n nodes, if each node is independently sampled with probability p =Ω(√log( n )/ k ), then the subgraph induced by the sampled nodes has vertex connectivity Ω( kp 2 ), with high probability. If edges are sampled with probability p = Ω(log ( n )/ k ), then the sampled subgraph has vertex connectivity Ω( kp ), with high probability. Both bounds are existentially optimal.

The dual graph model describes a radio network that contains both reliable and unreliable links. In recent years, this model has received significant attention by the distributed algorithms community [Kuhn/Lynch/Newport/Oshman/Richa, PODC 2010; Censor-Hillel/Gilbert/Kuhn/Lynch/Newport, Dist. Comp. 2014; Ghaffari/Haeupler/Lynch/Newport, DISC 2012; Ghaffari/Lynch/Newport, PODC 2013; Ghaffir/Kantor/Lynch/Newport, PODC 2014; Newport, DISC 2014; Ahmadi/Ghodselahi/Kuhn/Molla, OPODIS 2015; Lynch/Newport, PODC 2015]. Due to results in [Ghaffari/Lynch/Newport, PODC 2013], it is known that leader election plays a key role in enabling efficient computation in this difficult setting: a leader can synchronize the network in such a manner that most problems can be subsequently solved in time similar to the classical radio network model that lacks unreliable links. The feasibility of efficient leader election in the dual graph model, however, was left as an important open question. In this paper, we answer this question. In more detail, we prove new upper and lower bound results that characterize the complexity of leader election in this setting. By doing so, we reveal a surprising dichotomy: (1) under the assumption that the network size n is in the range 1 to N, where N is a large upper bound on the maximum possible network size (e.g., the ID space), leader election is fundamentally hard, requiring ~Omega(sqrt(N)) rounds to solve in the worst-case; (2) under the assumption that n is in the range 2 to N, however, the problem can be solved in only ~O(D) rounds, for network diameter D, matching the lower bound for leader election in the standard radio network model (within log factors) [Ghaffari/Haeupler, SODA 2013].

This paper presents the first (non-trivial) distributed planar embedding algorithm. We consider this a crucial first step in a broader program to design efficient distributed algorithms for planar networks. We work in the standard distributed model in which nodes can send an O(log n)-bit message to each of their neighbors per round. In a planar network, with n nodes and diameter D, our deterministic planar embedding algorithm uses O(D dot min{log n, D) rounds to compute a combinatorial planar embedding, which consists of each node knowing the clockwise order of its incident edges in a fixed planar drawing. The complexity of our algorithm is near-optimal and matches the trivial lower bound of Omega(D) up to a log n factor. No algorithm outperforming the trivial round complexity of O(n) was known prior to this work.

We present a randomized algorithm that computes a Minimum Spanning Tree (MST) in O(log* n) rounds, with high probability, in the Congested Clique model of distributed computing. In this model, the input is a graph on n nodes, initially each node knows only its incident edges, and per round each two nodes can exchange O(log n) bits. Our key technical novelty is an O(log* n) Graph Connectivity algorithm, the heart of which is a (recursive) forest growth method, based on a combination of two ideas: a sparsity-sensitive sketching aimed at sparse graphs and a random edge sampling aimed at dense graphs. Our result improves significantly over the O(log log log n) algorithm of Hegeman et al. [PODC 2015] and the O(log log n) algorithm of Lotker et al. [SPAA 2003; SICOMP 2005].

Consider n anonymous nodes each initially supporting an opinion in {1, 2, …, k} and suppose that they should all learn the opinion with the largest support. Per round, each node contacts a random other node and exchanges B bits with it, where typically B is at most O(log n).

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents a very simple randomized algorithm for this problem providing a near-optimal local complexity, which incidentally, when combined with some known techniques, also leads to a near-optimal global complexity.

This paper introduces the concept of low-congestion shortcuts for (near-)planar networks, and demonstrates their power by using them to obtain near-optimal distributed algorithms for problems such as Minimum Spanning Tree (MST) or Minimum Cut, in planar networks. Consider a graph G = (V, E) and a partitioning of V into subsets of nodes S1, …, SN, each inducing a connected subgraph G[Si]. We define an α-congestion shortcut with dilation β to be a set of subgraphs H1, …, HN ⊆ G, one for each subset Si, such that 1. For each i ∊ [1, N], the diameter of the subgraph G[Si] + Hi is at most β. 2. For each edge e ∊ E, the number of subgraphs G[Si] + Hi containing e is at most α. We prove that any partition of a D-diameter planar graph into individually-connected parts admits an O(D log D)-congestion shortcut with dilation O(D log D), and we also present a distributed construction of it in Õ(D) rounds. We moreover prove these parameters to be near-optimal; i.e., there are instances in which, unavoidably, . Finally, we use low-congestion shortcuts, and their efficient distributed construction, to derive Õ(D)-round distributed algorithms for MST and Min-Cut, in planar networks. This complexity nearly matches the trivial lower bound of Ω(D). We remark that this is the first result bypassing the well-known existential lower bound of general graphs (see Peleg and Rubinovich [FOCS'99]; Elkin [STOC'04]; and Das Sarma et al. [STOC'11]) in a family of graphs of interest.

Tree structures such as breadth-first search (BFS) trees and minimum spanning trees (MST) are among the most fundamental graph structures in distributed network algorithms. However, by definition, these structures are not robust against failures and even a single edge's removal can disrupt their functionality. A well-studied concept which attempts to circumvent this issue is Fault-Tolerant Tree Structures, where the tree gets augmented with additional edges from the network so that the functionality of the structure is maintained even when an edge fails. These structures, or other equivalent formulations, have been studied extensively from a centralized viewpoint. However, despite the fact that the main motivations come from distributed networks, their distributed construction has not been addressed before.

This paper studies the question of how to run many distributed algorithms, solving independent problems, together as fast as possible. Suppose that we want to run distributed algorithms A_1, ..., A_k in the CONGEST model, each taking at most $dilation$ rounds, and where for each network edge, at most $congestion$ messages need to go through it, in total over all these algorithms. A celebrated work of Leighton, Maggs, and Rao[Combinatorica 1994] shows that in the special case where each of these algorithms is simply a packet routing---that is, sending a message from a source to a destination along a given path---there is an $O(congestion+dilation)$ round schedule. Note that this bound is trivially optimal.

We present a near-optimal distributed algorithm for (1+o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D+ √n)⋅ no(1) communication rounds in the Congest model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound.

We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest.

In the directed single-source reachability problem, input is a directed graph G=(V, E) and a source node s, and the objective is to identify nodes t for which there is a directed path in G from s to t. Recently Nanongkai[STOC'14] presented a distributed algorithm that solves this problem in Õ(D+√nD1/2) rounds, where D and n respectively denote the network diameter and the number of nodes. This note presents an algorithm that slightly improves the round complexity to Õ(D+√nD1/4), thus getting closer to the ~Ω(D+√n) lower bound of Das Sarma et al.[STOC'11]

A fundamental result by Karger [10] states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log n/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability , then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp2), with high probability. This bound improves upon the recent results of Censor-Hillel et al. [6], and is existentially optimal.

We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any n-round interactive protocol using N rounds over an adversarial channel that corrupts up to ρN transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate ρ, communication complexity N, and computational complexity. We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized non-adaptive coding scheme has a near-linear computational complexity and tolerates any error rate δ1.

A fundamental problem in distributed network algorithms is to manage congestion and obtain information flow matching the graph's connectivity. In this paper, we present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. These decompositions allow us to achieve a flow with size close to the connectivity by parallelizing it along the trees. More specifically, our distributed decomposition algorithms are as follows: - A decomposition of each undirected graph with vertex-connectivity k into (fractionally) vertex-disjoint weighted dominating trees with total weight Ω(k/log n), in ~O(D+√n) rounds. - A decomposition of each undirected graph with edge-connectivity λ into (fractionally) edge-disjoint weighted spanning trees with total weight ⌈λ-1/2⌉(1-ε), in ~{O}(D+√nλ) rounds.

We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting away low-level details such as signal propagation and contention.We begin by studying upper and lower bounds for this problem in a standard abstract MAC layer model---identifying an interesting dependence between the structure of unreliable links and achievable time complexity. In more detail, given a restriction that devices connected directly by an unreliable link are not too far from each other in the reliable link topology, we can (almost) match the efficiency of the reliable case. For the related restriction, however, that two devices connected by an unreliable link are not too far from each other in geographic distance, we prove a new lower bound that shows that this efficiency is impossible. We then investigate how much extra power must be added to the model to enable a new order of magnitude of efficiency. In more detail, we consider an enhanced abstract MAC layer model and present a new multi-message broadcast algorithm that (under certain natural assumptions) solves the problem in this model faster than any known solutions in an abstract MAC layer setting.

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication. We show that there is a family of radio networks with a tight Θ(log log n) network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a Θ(log log n) factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds showing that the asymptotic worst-case broadcast throughput over all networks with n nodes is messages-per-round for both routing and network coding.

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are the classical results of Tutte and Nash-Williams from 1961 which show that a λ-edge-connected graph contains ⌊(λ − 1)/2⌋ edge-disjoint spanning trees. We argue that connected dominating set partitions and packings are the natural analogues of edge-disjoint spanning trees in the context of vertex connectivity and we use them to obtain structural results about vertex connectivity in the spirit of those for edge connectivity. More specifically connected dominating set (CDS) partitions and packings are counterparts of edge-disjoint spanning trees, focusing on vertex-disjointness rather than edge-disjointness, and their sizes are always upper bounded by the vertex connectivity k. We constructively show that every k-vertex-connected graph with n nodes has CDS packings and partitions with sizes, respectively, Ω(k/logn) and Ω(k/log5n), and we prove that the former bound is existentially optimal. Beautiful results by Karger show that when edges of a λedge-connected graph are independently sampled with probability p, the sampled graph has edge connectivity (λp). Obtaining such a result for vertex sampling remained open. We illustrate the strength of our approach by proving that when vertices of a k-vertex-connected graph are independently sampled with probability p, the graph induced by the sampled vertices has vertex connectivity (kp2). This bound is optimal up to poly-log factors and is proven by building an (kp2) size CDS packing on the sampled vertices while sampling happens. As an additional important application, we show CDS packings to be tightly related to the throughput of routing-based algorithms and use our new toolbox to yield a routing-based broadcast algorithm with optimal throughput Ω(k/log n + 1), improving the (previously best-known) trivial throughput of Θ(1).

We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings.

We present new upper bounds for fundamental problems in multichannel wireless networks. These bounds address the benefits of dynamic spectrum access, i.e., to what extent multiple communication channels can be used to improve performance. In more detail, we study a multichannel generalization of the standard graph-based wireless model without collision detection, and assume the network topology satisfies polynomially bounded independence.

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in O(D + log6 n) rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter D. It improves over the currently best known O(Dlogn/D + log2 n) algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection.

We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model [11, 12, 3, 8] assume an offline adaptive adversary - the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions.

We design leader election protocols for multi-hop radio networks that elect a leader in almost the same time TBC that it takes for broadcasting one message (one ID). For the setting without collision detection our algorithm runs whp. in rounds on any n-node network with diameter D. Since is a lower bound, our upper bound is optimal up to a factor of at most log log n and the extra log n factor on the additive term. Our algorithm is furthermore the first O(n) time algorithm for this setting. Our algorithm improves over a 23 year old simulation approach of Bar-Yehuda, Goldreich and Itai with a O(TBC log n) running time: In 1987 they designed a fast broadcast protocol and subsequently in 1989 they showed how it can be used to simulate one round of a single-hop network that has collision detection in TBC time. The prime application of this simulation was to simulate Willards single-hop leader election protocol, which elects a leader in O(log n) rounds whp. and O(log log n) rounds in expectation. While it was subsequently shown that Willards bounds are tight, it was unclear whether the simulation approach is optimal. Our results break this barrier and essentially remove the logarithmic slowdown over the broadcast time TBC. This is achieved by going away from the simulation approach. We also give an leader election algorithm for the setting with collision detection (even with single-bit messages). This is optimal up to log log n factors and improves over a deterministic algorithm that requires Θ(n) rounds independently of D. Our almost optimal leader election protocols are especially important because countless communication protocols in radio networks use leader election as a crucial first step to solve various, seemingly unrelated, communication primitives such as gathering, multiple unicasts or multiple broadcasts. Even though leader election seems easier than these tasks, its best-known O(TBC log n) running time had become a bottleneck, preventing optimal algorithms. Breaking the simulation barrier for leader election in this paper has subsequently led to the development of near optimal protocols for these communication primitives.

This article proposes a new distributed architecture for update message exchange inmassively multi-user virtual environments (MMVE). MMVE applications require delivery of updates among various locations in the virtual environment. The proposed architecture here exploits the location addressing of geometrical routing in order to alleviate the need for IP-specific queries. However, the use of geometrical routing requires careful choice of overlay to achieve high performance in terms of minimizing the delay. At the same time, the MMVE is dynamic, in sense that users are constantly moving in the 3D virtual space. As such, our architecture uses a distributed topology control scheme that aims at maintaining the requires QoS to best support the greedy geometrical routing, despite user mobility or churn. We will further prove the functionality and performance of the proposed scheme through both theory and simulations.

In this paper, we propose the object pursuing based efficient routing algorithm (OPERA) suitable for vehicular ad hoc networks (VANETs), esp. in sparse situations. The proposed algorithm is applicable for both moving and fixed destinations. It is based on considering static nodes at each intersection. In this algorithm, we optimize the decision making at intersections, with respect to the connectivity and feasibilty of the roads. To this end, we consider the average delay of each road as the connectivity metric, and the vehicle availability in the transmission range of the intersection as the feasibility metric. By exploiting the related metrics, we select the next road to forward the packet in order to minimize the overall delay. We also include a pursuing phase in our algorithm, in order to capture the moving destinations. The simulation results indicate the superiority of our proposed algorithm, compared to previous ones.