We provide a fast witness-sensitive algorithm for detecting an induced diamond (a K₄ minus an edge) in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^2.425/t^0.25 + n², n^ω)) with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time O(n^ω log n) [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever t ≥ n^{(3-ω)/3}, where ω < 2.372 is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is r-heavy if this size is at least r, and we provide a fast detection algorithm for r-heavy diamonds in Õ(r⋅(n/r)^ω + (n/r)³+ nr) time. When there are no r-heavy diamonds, we provide a different fast detection algorithm in Õ(MM(n,n,n√{r/t})) time, where MM(a,b,c) denotes the time to multiply an a × b matrix by a b × c matrix, which is conditionally optimal for r = Õ(1). Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no r-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for 4-SUM and for a special case of 4-cycles.

We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph G* of a known base graph G is realized by including each edge e independently with a known probability pe, and we must solve an optimization problem on G* despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of G to learn if the edge exists in G*, and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in G* (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds.

We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of $O(n\log{n})$-bit input per node can be solved in roughly $n$ rounds, where $n$ is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm $\mathcal{A}$ for the non-faulty Congested Clique model, we show how to transform it into an algorithm $\mathcal{A}'$ for the faulty model, with an overhead that could be as small as some logarithmic-in-$n$ factor, by considering refined complexity measures of $\mathcal{A}$. As an exemplifying application of our approach, we show that the $O(n^{1/3})$-round complexity of semi-ring matrix multiplication [Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail $99\%$ of the nodes (or any other constant fraction).

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

We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a (1±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal.

Fault tolerance is a major concern in distributed computational settings. In the classic master-worker setting, a server (the master) needs to perform some heavy computation which it may distribute to m other machines (workers) in order to speed up the time complexity. In this setting, it is crucial that the computation is made robust to failed workers, in order for the master to be able to retrieve the result of the joint computation despite failures. A prime complexity measure is thus the recovery threshold, which is the number of workers that the master needs to wait for in order to derive the output. This is the counterpart to the number of failed workers that it can tolerate. In this paper, we address the fundamental and well-studied task of matrix multiplication. Specifically, our focus is on when the master needs to multiply a batch of n pairs of matrices. Several coding techniques have been proven successful in reducing the recovery threshold for this task, and one approach that is also very efficient in terms of computation time is called Rook Codes. The previously best known recovery threshold for batch matrix multiplication using Rook Codes is $$O(n^{\log _2{3}})=O(n^{1.585})$$ . Our main contribution is a lower bound proof that says that any Rook Code for batch matrix multiplication must have a recovery threshold that is at least $$\omega (n)$$ . Notably, we employ techniques from Additive Combinatorics in order to prove this, which may be of further interest. Moreover, we show a Rook Code that achieves a recovery threshold of $$n^{1+o(1)}$$ , establishing a near-optimal answer to the fault tolerance of this coding scheme.

The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size p in $$n^{1 - 2/p + o(1)}$$ rounds in the Congest model. For triangles, our $$n^{1/3+o(1)}$$ round complexity improves upon the previous state of the art of $$n^{2/3+o(1)}$$ rounds (Chang and Saranurak, in: 2020 IEEE 61st annual symposium on foundations of computer science (FOCS), pp 377–388. IEEE Computer Society, Los Alamito, 2020. https://doi.org/10.1109/FOCS46700.2020.00043 ). For cliques of size $$p \ge 4$$ , ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values $$p \ge 3$$ our algorithms are tight up to an $$n^{o(1)}$$ subpolynomial factor, which comes from the deterministic routing procedure we use.

Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes $\{\mathsf{cycles, trees, forests, chordal, cactus, even\text{-}hole\text{-}free, claw\text{-}free}\}$, there are schedules that use $O(\varepsilon^{-1})$ batches and incur only a $1+\varepsilon$ multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in $O(\varepsilon^{-1}\log^* n)$ distributed time, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.

Many exceptionally high-quality doctoral dissertations were submitted for the 2022 Principles of Distributed Computing Doctoral Dissertation Award. After careful long deliberation, the award committee decided to share the award among two:

We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible.

This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted variants of subgraph finding problems in various models of distributed computing, and states intriguing open questions.

In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph $G=(V,E)$, the goal is to find a cut $S\subseteq V$ that maximizes the total weight of edges that cross $S$ even after an adversary removes $k$ vertices from $G$. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures $k$ we present an approximation of $(0.878-ε)$ against an adaptive adversary and of $α_{GW}\approx 0.8786$ against an oblivious adversary (here $α_{GW}$ is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of $α_{GW}$ against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.

No abstract available.

In this paper we consider the fundamental problem of finding subgraphs in highly dynamic distributed networks -- networks which allow an arbitrary number of links to be inserted / deleted per round. We show that the problems of k-clique membership listing (for any k≥ 3), 4-cycle listing and 5-cycle listing can be deterministically solved in O(1)-amortized round complexity, even with limited logarithmic-sized messages.

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

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

A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.

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

This issue of SICOMP contains 14 specially selected papers from the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), held June 18--June 21, 2016, in Cambridge, Massachusetts. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee members were Alexandr Andoni, Sanjeev Arora, Allison Bishop, Avrim Blum, Keren Censor-Hillel, Timothy Chan, Chandra Chekuri, Jing Chen, Zeev Dvir, Fabrizio Grandoni, Parikshit Gopalan, Kasper Green Larsen, Huijia (Rachel) Lin, Konstantin Makarychev, Yishay Mansour (chair), Jakob Nordström, Debmalya Panigrahi, Prasad Raghavendra, Sofya Raskhodnikova, R Ravi, Mario Szegedy, Êva Tardos, Salil Vadhan, Avi Wigderson, and Ronald de Wolf. We briefly describe here the papers that appear in this special issue. In “Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders,” Shahar Dobzinski provides the first truthful mechanism for welfare maximization in combinatorial auctions with submodular bidders whose approximation ratio is $O(\sqrt{\log m})$. Previously the best ratio was $O(\log m)$. In “A Tight Space Bound for Consensus,” Leqi Zhu proves that every randomized wait-free (or obstruction-free) consensus protocol for $n$ processes must use at least $n-1$ registers. Previously, this bound was known only in the anonymous setting, while for the general case only a $\sqrt{n}$ bound was known. In “Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs,” Gil Cohen constructs a $2^{(\log\log n)^c}$-Ramsey graph for some universal constant $c$, a significant improvement in this direction. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two $n$-bit sources with entropy ${polylog}(n)$. Previously, such dispersers could only support entropy $\Omega(n)$. In “Algorithmic Bayesian Persuasion,” Shaddin Dughmi and Haifeng Xu examines Bayesian persuasion through a computational lens for the first time. When the payoff distributions are i.i.d. across actions, the authors provide a polynomial-time optimal solution and a “simple” $(1-1/e)$-approximation. For independent but nonidentical distributions, \#P-hardness is proved. For the general case with a black-box sampling oracle, an FPTAS is provided and shown to be the best possible under the black-box model. In “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths,” Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai present a deterministic $(1 + o(1))$-approximation algorithm for solving the single-source shortest paths problem on distributed weighted networks in $O(n^{1/2+o(1)} + D^{1+o(1)})$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. This improves upon previous results in being deterministic and completing in less time or in obtaining a smaller approximation factor. Moreover, it is almost tight due to a known lower bound. In “Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines,” Nikhil Bansal, Aravind Srinivasan, and Ola Svensson improve, by a small but fixed constant, the long-standing approximation factor of $3/2$ for the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. In “A Duality-Based Unified Approach to Bayesian Mechanism Design,” Yang Cai, Nikhil Devanur, and Seth Matthew Weinberg provide a duality-based unified framework for designing simple and approximately optimal auctions. Using this framework, the authors prove that either a posted-price mechanism or the Vickrey--Clarke--Groves auction with per-bidder entry fees achieves a constant-factor of the optimal revenue achievable by a Bayesian Incentive Compatible mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. and Yao, and improving both approximation ratios. In “A $(1+\varepsilon)$-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies,” Elaine Levey and Thomas Rothvoss consider the problem of scheduling $n$ unit size jobs with a precedence order on $m$ identical machines as to minimize the makespan. They prove that for any fixed $\epsilon$ and $m$, an LP-hierarchy lift of the time-indexed LP with a slightly super poly-logarithmic number of $r = (\log n)^{\Theta(\log \log n)}$ rounds provides a $(1 + \epsilon)$-approximation. The previous best approximation algorithms for this problem guarantee a $(2 - 7/(3m+1))$-approximation in polynomial time for $m \ge 4$ and $4/3$ for $m=3$. In “Bipartite Perfect Matching Is in Quasi-${{NC}}$,” Stephen Fenner, Rohit Gurjar, and Thomas Thierauf show that the bipartite perfect matching problem is in quasi-${{NC}}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. In “Exponential Separation of Communication and External Information,” Anat Ganor, Gillat Kol, and Ran Raz prove the first gap, an exponential gap, between external information complexity and communication complexity of a communication task. Previously such a separation was known only for the internal information vs communication complexity. This result has implication to the question of compressing communication protocols to the amount of information they reveal about the inputs. In “Constant-Round Interactive Proofs for Delegating Computation,” Omer Reingold, Guy Rothblum, and Ron Rothblum design efficient, constant-round interactive proofs. They show that for any statement that can be evaluated in polynomial time and space $S$, there exists a constant-round interactive protocol where the prover has polynomial runtime and the verifier has a runtime of about $n+\poly(S)$. Prior to this work, very little was known about the power of constant-round protocol. This result is a major step for the grand challenge of verifiable delegation of computation. In “Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem,” Sepehr Assadi, Sanjeev Khanna, and Yang Li resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover (for any $\alpha= o(\sqrt{n})$) using a single-pass streaming algorithm, they show that $\Theta(mn/\alpha)$ space is both sufficient and necessary (up to an $O(\log n)$ factor), where $m$ denotes number of the sets and $n$ denotes size of the universe. They further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and achieve an additional saving of a factor of $\alpha$ in the space complexity, which is also the best possible. In “A Polynomial Lower Bound for Testing Monotonicity,” Aleksandrs Belovs and Eric Blais show a polynomial lower bound on query complexity for adaptive testers of monotonicity of an $n$-variate Boolean function. Prior to this work, similar lower bounds were known only for the nonadaptive testers, and proving similar bounds for adaptive testers has been a major challenge. In “Algorithmic Stability for Adaptive Data Analysis,” Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman take a solid step forward in the area of adaptive data analysis by establishing a clean, tight connection between the notion of differential privacy (max-KL stability) and design of adaptive queries. This connection improves a number of bounds that were known prior to this paper, and generalizes to handle more “data analysis" settings. We thank the authors, the program committee members, and the reviewers for STOC 2016 for their hard work, and we especially thank the SICOMP reviewers for their work in evaluating submitted papers.

We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the distributed setting, providing both algorithmic and hardness results. Our main hardness result shows that an $\alpha$-approximation for the minimum directed $k$-spanner problem for $k \geq 5$ requires $\Omega(n /\sqrt{\alpha}\log{n})$ rounds using deterministic algorithms or $\Omega(\sqrt{n }/\sqrt{\alpha}\log{n})$ rounds using randomized ones, in the Congest model of distributed computing. Combined with the constant-round $O(n^{\epsilon})$-approximation algorithm in the Local model of [L. Barenboim, M. Elkin, and C. Gavoille, Theoret. Comput. Sci., 751 (2016), pp. 2--23], as well as a polylog-round $(1+\epsilon)$-approximation algorithm in the Local model that we show here, our lower bounds for the Congest model imply a strict separation between the Local and Congest models. Notably, to the best of our knowledge, this is the first separation between these models for a local approximation problem. Similarly, a separation between the directed and undirected cases is implied. We also prove hardness results for weighted $k$-spanners and for unweighted undirected $k$-spanners for $k \geq 4$ in the Congest model. In addition, we show lower bounds for the minimum weighted 2-spanner problem in the Congest and Local models. On the algorithmic side, apart from the aforementioned $(1+\epsilon)$-approximation algorithm for minimum $k$-spanners, our main contribution is a new distributed construction of minimum 2-spanners that uses only polynomial local computations. Our algorithm has a guaranteed approximation ratio of $O(\log(m/n))$ for a graph with $n$ vertices and $m$ edges, which matches the best known ratio for polynomial-time sequential algorithms [G. Kortsarz and D. Peleg, J. Algorithms, 17 (1994), pp. 222--236], and is tight if we restrict ourselves to polynomial local computations. An algorithm with this approximation factor was not previously known for the distributed setting. The number of rounds required for our algorithm is $O(\log{n}\log{\Delta})$ with high probability, where $\Delta$ is the maximum degree in the graph. Our approach allows us to extend our algorithm to work also for the directed, weighted, and client-server variants of the problem. It also provides a Congest algorithm for the minimum dominating set problem, with a guaranteed $O(\log{\Delta})$ approximation ratio.

This article proves strong lower bounds for distributed computing in the congest model, by presenting the bit-gadget : a new technique for constructing graphs with small cuts. The contribution of bit-gadgets is twofold. First, developing careful sparse graph constructions with small cuts extends known techniques to show a near-linear lower bound for computing the diameter, a result previously known only for dense graphs. Moreover, the sparseness of the construction plays a crucial role in applying it to approximations of various distance computation problems, drastically improving over what can be obtained when using dense graphs. Second, small cuts are essential for proving super-linear lower bounds, none of which were known prior to this work. In fact, they allow us to show near-quadratic lower bounds for several problems, such as exact minimum vertex cover or maximum independent set, as well as for coloring a graph with its chromatic number. Such strong lower bounds are not limited to NP-hard problems, as given by two simple graph problems in P, which are shown to require a quadratic and near-quadratic number of rounds. All of the above are optimal up to logarithmic factors. In addition, in this context, the complexity of the all-pairs-shortest-paths problem is discussed. Finally, it is shown that graph constructions for congest lower bounds translate to lower bounds for the semi-streaming model, despite being very different in its nature.

Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.

This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an $O(1)$ amortized time complexity, (2) using only $O(\log{n})$-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, $(degree+1)$-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.

We investigate graph problems in the following setting: we are given a graph G and we are required to solve a problem on G2. While we focus mostly on exploring this theme in the distributed CONGEST model, we also show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on G2 would be quite difficult to solve efficiently on G, due to congestion. However, we show that the picture is both more complicated and more interesting.

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

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

The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G , such that \(T \cup Aug\) is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JáJá (SIAM J Comput 10(2):270–283, 1981 ). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (ACM Trans Algorithms 12(2):23, 2016 ). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC 2018), 2018 ), and approximations better than 2 for bounded weights (Adjiashvili in: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms (SODA), 2017 ; Fiorini et al. in: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018 . https://doi.org/10.1137/1.9781611975031.53 ). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O ( h ) rounds, where h is the height of T . When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in \(O(D+\sqrt{n}\log ^*{n})\) rounds, where n is the number of vertices and D is the diameter of G . Immediate consequences of our results are an O ( D )-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an \(O(h_{MST}+\sqrt{n}\log ^{*}{n})\) -round 3-approximation algorithm for the weighted case, where \(h_{MST}\) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.

This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send \(O(\log n)\) -bit messages in each round of communication. Our framework mostly follows by the derandomization approach of Luby (J Comput Syst Sci 47(2):250–286, 1993) combined with the power of all to all communication. Our key results are as follows: first, we show that in the congested clique model, which allows all-to-all communication, there is a deterministic maximal independent set algorithm that runs in \(O(\log ^2 {\varDelta })\) rounds, where \({\varDelta }\) is the maximum degree. When \({\varDelta }=O(n^{1/3})\) , the bound improves to \(O(\log {\varDelta })\) . In addition, we deterministically construct a \((2k-1)\) -spanner with \(O(kn^{1+1/k}\log n)\) edges in \(O(k \log n)\) rounds in the congested clique model.

We investigate a distributed maximal independent set reconfiguration problem , in which there are two MIS for which every node is given its membership status, and the nodes need to communicate with their neighbors to find a reconfiguration schedule from the first MIS to the second. We forbid two neighbors to change their membership status at the same step. We provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O ( MIS + R32 ) rounds. For bounded degree graphs, this is O ( log ⁎ ⁡ n ) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.

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

This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: - The bandwidth complexity of 1-round dynamic triangle detection or listing is Theta(1). - The bandwidth complexity of 1-round dynamic triangle membership listing is Theta(1) for node/edge deletions, Theta(n^{1/2}) for edge insertions, and Theta(n) for node insertions. - The bandwidth complexity of 1-round dynamic triangle membership detection is Theta(1) for node/edge deletions, O(log n) for edge insertions, and Theta(n) for node insertions. Most of our upper and lower bounds are tight. Additionally, we provide almost always tight upper and lower bounds for larger cliques.

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

The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random. In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a non-adaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of $\mathrm{poly}(\log Δ, \log \log n)$ rounds where $n$ is the number nodes in the network and $Δ$ is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not non-adaptive, it can be simulated with a multiplicative $O(Δ\log ^2 Δ)$ cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of $o(\log Δ)$ are unlikely to exist by proving that an $Ω(\log Δ)$ multiplicative round overhead is necessary under certain natural assumptions.

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network. Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.

Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of O~(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Keren Censor{-}Hillel et al., 2016]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph.

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.

A minimum spanning tree (MST) is an essential structure for distributed algorithms, since it is a low-cost connected subgraph which provides an efficient way to communicate in a network. However, trees cannot survive even one link failure. In this paper, we study the Tree Augmentation Problem (TAP), for which the input is a graph G and a spanning tree T of G and the goal is to augment T with a minimum (or minimum weight) set of edges Aug from G, such that T ∪ Aug remains connected after a failure of any single link.

The widely-studied radio network model [Chlamtac and Kutten, 1985] is a graph-based description that captures the inherent impact of collisions in wireless communication. In this model, the strong assumption is made that node v receives a message from a neighbor if and only if exactly one of its neighbors broadcasts. We relax this assumption by introducing a new noisy radio network model in which random faults occur at senders or receivers. Specifically, for a constant noise parameter p ∈ [0,1), either every sender has probability p of transmitting noise or every receiver of a single transmission in its neighborhood has probability p of receiving noise.

We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.

We present a simple deterministic distributed (2 + ϵ)-approximation algorithm for minimum-weight vertex cover, which completes in O (log Δ/ϵlog log Δ) rounds, where Δ is the maximum degree in the graph, for any ϵ > 0 that is at most O (1). For a constant ϵ, this implies a constant approximation in O (log Δ/log log Δ) rounds, which contradicts the lower bound of [KMW10].

In this paper, we study how a collection of interconnected nodes can efficiently perform a global computation in the $\mathcal{GOSSIP}$ model of communication. In this model nodes do not know the global topology of the network and may only initiate contact with a single neighbor in each round. This contrasts with the much less restrictive $\mathcal{LOCAL}$ model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In the $\mathcal{LOCAL}$ model this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the $\mathcal{GOSSIP}$ model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm, in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance $\phi$ and graph size $n$, culminating in a bound of $\Theta(\phi^{-1} \log n)$. In this paper, we give the first protocol that works efficiently on any topology. In particular we give an algorithm that solves the information dissemination problem in at most $O(D+\text{polylog}{(n)})$ rounds in a network of diameter $D$, with no dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of $D$. In fact, we prove that something stronger is true: any algorithm that requires $T$ rounds in the $\mathcal{LOCAL}$ model can be simulated in $O(T +\mathrm{polylog}(n))$ rounds in the $\mathcal{GOSSIP}$ model. We thus prove that these two models of distributed computation are equivalent up to an additive polylogarithmic term.

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.

We present a simple deterministic distributed (2+ε) approximation algorithm for minimum weight vertex cover, which completes in O(logδ/εlog logδ) rounds, where δ is the maximum degree in the graph, for any ε > 0 which is at most O(1). For a constant ε, this implies a constant approximation in Ologδ/log log δ) rounds, which contradicts the lower bound of [KMW10].

Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributed computing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either synchronous or asynchronous, with only a single adjustment and in a single round, in expectation. These strong guarantees hold for the complete fully dynamic setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former.

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. Although obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most nonblocking commercial code is only lock-free. This article suggests a simple solution to this problem. We show that for a large class of lock-free algorithms, under scheduling conditions that approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can continue to design simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes to the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1 but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst-case adversary, in a stochastic model capturing their expected asymptotic behavior.

Concurrent objects play a key role in the design of applications for multicore architectures, making it imperative to precisely understand their complexity requirements. For some objects, it is known that implementations can be significantly more efficient when their usage is restricted. However, apart from the specific restriction of one-shot implementations, where each process may apply only a single operation to the object, very little is known about the complexities of objects under general restrictions. This paper draws a more complete picture by defining a large class of objects for which an operation applied to the object can be “perturbed” $L$ consecutive times, and by proving lower bounds on their space complexity and on the time complexity of deterministic implementations of such objects. This class includes bounded-value max registers, limited-use approximate and exact counters, and limited-use collect and compare-and-swap objects; $L$ depends on the number of times the object can be accessed or the maximum value it can support. For $n$-process implementations that use only historyless primitives, we prove $\Omega( \min( L, n ))$ space complexity lower bounds, which hold for both deterministic and randomized implementations. For deterministic implementations, we prove lower bounds of $\Omega(\min(\log L, n))$ on the worst-case step complexity of an operation. When arbitrary primitives can be used, we prove that either some operation incurs $\Omega(\min(\log L, n))$ memory stalls or some operation performs $\Omega(\min(\log L, n))$ steps. In addition to our deterministic time lower bounds, the paper establishes lower bounds on the expected step complexity of restricted-use randomized versions of many of these objects in a weak oblivious adversary model.

In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1-2/ω) round matrix multiplication algorithm, where ω < 2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) triangle counting algorithm of Dolev et al. [DISC 2012], a (1 + o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the ~O (n1/2)-round (2 + o(1))-approximation algorithm of Nanongkai [STOC 2014], and computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles.

A fundamental challenge in designing concurrent data structures is obtaining efficient wait-free implementations, in which each operation completes regardless of the behavior of other operations in the system. The most common paradigm for guaranteeing wait-freedom is to employ a helping mechanism, in which, intuitively, fast processes help slow processes complete their operations. Curiously, despite its abundant use, to date, helping has not been formally defined nor was its necessity rigorously studied. In this paper we initiate a rigorous study of the interaction between wait-freedom and helping. We start with presenting a formal definition of help, capturing the intuition of one thread helping another to make progress. Next, we present families of object types for which help is necessary in order to obtain wait-freedom. In other words, we prove that for some types there are no linearizable wait-free help-free implementations. In contrast, we show that other, simple types, can be implemented in a linearizable wait-free manner without employing help. Finally, we provide a universal strong primitive for implementing wait-free data structures without using help. Specifically, given a wait-free help-free fetch&cons object, one can implement any type in a wait-free help-free manner.

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.

This article presents a novel implementation of a snapshot object for n processes, with O (log 2 b log n ) step complexity for update operations and O (log b ) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes. For polynomially many updates, this is an exponential improvement on previous snapshot algorithms, which have linear step complexity. It overcomes the existing Ω( n ) lower bound on step complexity by having the step complexity depend on the number of updates. The key to this implementation is the construction of a new object consisting of a pair of max registers that supports a scan operation.

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free.

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.

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).

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free.

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of Ω( k ) process steps for deterministic renaming into any namespace of size subexponential in k , where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of Ω( k log ( k / c )) on the total step complexity of renaming into a namespace of size ck , for any c ≥ 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O (log k ), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.

This paper presents a novel implementation of a snapshot object for n processes, with O(log2blogn) step complexity for update operations and O(logb) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes.

Concurrent objects play a key role in the design of applications for multi-core architectures, making it imperative to precisely understand their complexity requirements. For some objects, it is known that implementations can be significantly more efficient when their usage is restricted. However, apart from the specific restriction of one-shot implementations, where each process may apply only a single operation to the object, very little is known about the complexities of objects under general restrictions.

In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In the LOCAL model, this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the GOSSIP model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm, in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance φ and graph size n, culminating in a bound of O(φ-1 log n).

This article presents constructions of useful concurrent data structures, including max registers and counters, with step complexity that is sublinear in the number of processes, n . This result avoids a well-known lower bound by having step complexity that is polylogarithmic in the number of values the object can take or the number of operations applied to it. The key step in these implementations is a method for constructing a max register , a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed m , an m -valued max register is constructed from one-bit multi-writer multi-reader registers at a cost of at most ⌈log m ⌉ atomic register operations per write or read. An unbounded max register is constructed with cost O (min(log v , n )) to read or write a value v . Max registers are used to transform any monotone circuit into a wait-free concurrent data structure that provides write operations setting the inputs to the circuit and a read operation that returns the value of the circuit on the largest input values previously supplied. One application is a simple, linearizable, wait-free counter with a cost of O (min(log n log v , n )) to perform an increment and O (min(log v , n )) to perform a read, where v is the current value of the counter. For polynomially-many increments, this becomes O (log 2 n ), an exponential improvement on the best previously known upper bounds of O ( n ) for exact counting and O ( n 4/5+ϵ ) for approximate counting. Finally, it is shown that the upper bounds are almost optimal. It is shown that for deterministic implementations, even if they are only required to satisfy solo-termination, min(⌈log m ⌉, n -1) is a lower bound on the worst-case complexity for an m -valued bounded max register, which is exactly equal to the upper bound for m ≤ 2 n -1 , and min( n -1, ⌈ log m ⌉ - log(⌈ log m ⌉ + k )) is a lower bound for the read operation of an m -valued k -additive-accurate counter, which is a bounded counter in which a read operation is allowed to return a value within an additive error of ± k of the number of increment operations linearized before it. Furthermore, even in a solo-terminating randomized implementation of an n -valued max register with an oblivious adversary and global coins, there exist simple schedules in which, with high probability, the worst-case step complexity of a read operation is Ω(log n /log log n ) if the write operations have polylogarithmic step complexity.

Gathering data from nodes in a network is at the heart of many distributed applications, most notably while performing a global task. We consider information spreading among $n$ nodes of a network, where each node $v$ has a message $m(v)$ which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running time bounds for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, in which information is exchanged within well-connected components, and then sending messages across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has large weak conductance, from a polynomial to a polylogarithmic number of rounds.

We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate k distinct messages to all n nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of O((k + log n + D)Δ) rounds with high probability, where D and Δ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of k this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is Θ(k + D).

In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [4,9,10]. This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process u is provided a local link detector set consisting of every neighbor connected to u by a reliable link. The algorithm solves the CCDS problem in O(Δ\log2 n/b + log3 n) rounds, with high probability, where Δ is the maximum degree in the reliable link graph, n is the network size, and b is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in log3 n time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in O(Δpolylog(n)) time under the assumption of O(1) unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process's local link detector set is sufficient to require Ω(Δ) rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time.

Gathering data from nodes in a network is at the heart of many distributed applications, most notably, while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running times for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, after which messages are sent across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has a large weak conductance, from polynomial to polylogarithmic number of rounds. We demonstrate the power of fast information spreading in accomplishing global tasks on the leader election problem, which lies at the core of distributed computing. Our results yield an algorithm for leader election that has a scalable running time on graphs with large weak conductance, improving significantly upon previous results.

This paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c ≥ 1.

This paper presents wait-free randomized algorithms for solving set-agreement in asynchronous shared-memory systems under a strong adversary. First, the definition of a shared-coin algorithm is generalized to a multi-sided shared-coin algorithm, and it is shown how to use any multi-sided shared coin in order to obtain a randomized set-agreement algorithm for agreeing on k values out of k+1. Then, an implementation is given for a (k+1)-sided shared coin for n processes with a constant agreement parameter, O(n2/k) total step complexity, and O(n/k) individual step complexity. This implementation yields a randomized set-agreement algorithm for agreeing on k values out of k+1 with a total step complexity of O(n2/k + nk) and an individual step complexity of O(n/k + k). Next, other set-agreement algorithms for agreeing on l values out of k+1, where l is smaller than k, are presented. This includes the case of multi-valued consensus in which l=1, k >1. To the best of our knowledge, these are the first wait-free algorithms for set-agreement in the asynchronous shared-memory model under a strong adversary that are not for the specific case of binary consensus, where l= k = 1. Finally, an application of asynchronous wait-free multi-valued consensus is presented, in implementing at-most-once semantics with optimal effectiveness.

This paper studies the inherent trade-off between termination probability and total step complexity of randomized consensus algorithms. It shows that for every integer k, the probability that an f-resilient randomized consensus algorithm of n processes does not terminate with agreement within $k(n-f)$ steps is at least $\frac{1}{c^k}$, for some constant c. A corresponding result is proved for Monte-Carlo algorithms that may terminate in disagreement. The lower bound holds for asynchronous systems, where processes communicate either by message passing or through shared memory, under a very weak adversary that determines the schedule in advance, without observing the algorithm's actions. This complements algorithms of Kapron et al. [Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2008, pp. 1038–1047] for message-passing systems, and of Aumann [Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM, New York, 1997, pp. 209–218] and Aumann and Bender [Distrib. Comput., 17 (2005), pp. 191–207] for shared-memory systems.

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n -1 crash failures. For any fixed ϵ, the counter achieves a relative error of δ with high probability, at the cost of O (((1/δ) log n ) O (1/ϵ) ) register operations per increment and O ( n 4/5+ϵ ((1/δ) log n ) O (1/ϵ) ) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes. An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O ( n log n ) to an optimal O ( n ), resolving one of the last remaining open problems concerning consensus in this model.

A method is given for constructing a max register, a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed m, an m-valued max register can be constructed from one-bit multi-writer multi-reader registers at a cost of at most [lg m] atomic register operations per write or read. The construction takes the form of a binary search tree: applying classic techniques for building unbalanced search trees gives an unbounded max register with cost O(min(log v, n)) to read or write a value v, where n is the number of processes.

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ∊, the counter achieves a relative error of δ with high probability at the cost of O(((1/δ)log n)O(1/∊)) register operations per increment and O(n4/5+∊((1/δ)log n)O(1/∊)) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes. An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.

This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary. The fastest previously known algorithm requires a process to perform an expected O(n log2 n) read and write operations in the worst case. In our algorithm, each process executes at most an expected O(n log n) read and write operations. It is shown that shared-coin algorithms can be combined together to yield an algorithm with O(n log n) individual work and O(n2) total work.

This paper studies the inherent trade-off between termination probability and total step complexity of randomized consensus algorithms. It shows that for every integer k, the probability that an f-resilient randomized consensus algorithm of n processes does not terminate with agreement within k(n-f) steps is at least 1/ck, for some constant c.

A distributed consensus algorithm allows n processes to reach a common decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in an asynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminate with probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity , which is the expected total number of steps taken by all processes. This article proves that the total step complexity of randomized consensus is Θ( n 2 ) in an asynchronous shared memory system using multi-writer multi-reader registers. This result is achieved by improving both the lower and the upper bounds for this problem. In addition to improving upon the best previously known result by a factor of log 2 n , the lower bound features a greatly streamlined proof. Both goals are achieved through restricting attention to a set of layered executions and using an isoperimetric inequality for analyzing their behavior. The matching algorithm decreases the expected total step complexity by a log n factor, by leveraging the multi-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithm as a stochastic process and applying Kolmogorov's inequality.

A distributed consensus algorithm allows n processes to reach acommon decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in anasynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminatewith probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes.

A binary sequence satisfies a one-dimensional (d, k) constraint if every run of zeroes has length at least d and at most k. A binary two-dimensional array satisfies a (d, k) constraint if every run of zeroes, in each one of the array directions, has length at least d and at most k. Few models have been proposed in the literature to handle two dimensional data: the diamond model, the square model, the hexagonal model, and the triangular model. The constraints in the different directions might be asymmetric and hence many kind of constraints are defined depending on the number of directions in the model. For example, a two-dimensional array in the diamond model satisfies a (d1, k1, d2, k2) constraint if it satisfies the one-dimensional (d1,k1) constraint horizontally and the one-dimensional (d2,k2) constraint vertically. In this paper we examine the region in which the capacity of the constraints is zero or positive in the various models. We consider asymmetric constraints in the diamond model and symmetric constraints in the other models. In particular we provide an almost complete solution for asymmetric constraints in the diamond model

A binary sequence satisfies a one-dimensional (d,k) constraint if every run of zeros (with possible exception of the first and the last runs) has length at least d and at most k. A binary two-dimensional array satisfies a (d,k) constraint if each row and each column satisfies the one-dimensional (d,k) constraint. Few models have been proposed in the literature to handle two-dimensional data: the diamond model, the square model, the hexagonal model, and the triangular model. The constraints in the different directions might be asymmetric and hence many kind of constraints are defined depending on the number of directions in the model. For example, a two-dimensional array in the diamond model satisfies a (d1,k1,d2,k2) constraint if it satisfies the one-dimensional (d1,k1) constraint horizontally and the one-dimensional (d2,k2) constraint vertically. In this correspondence, the region in which the capacity is zero or positive, in the various models, is examined. Asymmetric constraints in the diamond model and symmetric constraints in the other models are considered. In particular, an almost complete solution for asymmetric constraints in the diamond model is provided