A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. This paper introduces several classes of distributed decision problems, proves separation among them and presents some complete problems. More specifically, we consider the standard LOCAL model of computation and define LD (for local decision) as the class of decision problems that can be solved in constant number of communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD, and ask whether LD=BPLD. We provide a partial answer to this question by showing that in many cases, randomization does not help for deciding hereditary languages. In addition, we define the notion of local many-one reductions, and introduce the (nondeterministic) class NLD of decision problems for which there exists a certificate that can be verified in constant number of communication rounds. We prove that there exists an NLD-complete problem. We also show that there exist problems not in NLD. On the other hand, we prove that the class NLD#n, which is NLD assuming that each processor can access an oracle that provides the number of nodes in the network, contains all (decidable) languages. For this class we provide a natural complete problem as well.
The question of what can be computed in a constant number of communication rounds was investigated in the seminal work of Naor and Stockmeyer @cite_16 . In particular, that paper considers a subclass of @math , called LCL, which is essentially @math restricted to languages involving graphs of constant maximum degree, and involving processor inputs taken from a set of constant size, and studies the question of how to compute in @math rounds the constructive versions of decision problems in LCL. The paper provides some beautiful general results. In particular, the authors show that if there exists a randomized algorithm that constructs a solution for a problem in LCL in @math rounds, then there is also a deterministic algorithm constructing a solution for this problem in @math rounds. Unfortunately, the proof of this result relies heavily on the definition of LCL. Indeed, the constant bound constraints on the degrees and input sizes allow the authors to cleverly use Ramsey theory. It is thus not clear whether it is possible to extend this result to all languages in @math .
@cite_16
2017345786
The celebrated Time Hierarchy Theorem for Turing machines states, informally, that more problems can be solved given more time. The extent to which a time hierarchy-type theorem holds in the distributed LOCAL model has been open for many years. It is consistent with previous results that all natural problems in the LOCAL model can be classified according to a small constant number of complexities, such as @math , etc. In this paper we establish the first time hierarchy theorem for the LOCAL model and prove that several gaps exist in the LOCAL time hierarchy. 1. We define an infinite set of simple coloring problems called Hierarchical @math -Coloring . A correctly colored graph can be confirmed by simply checking the neighborhood of each vertex, so this problem fits into the class of locally checkable labeling (LCL) problems. However, the complexity of the @math -level Hierarchical @math -Coloring problem is @math , for @math . The upper and lower bounds hold for both general graphs and trees, and for both randomized and deterministic algorithms. 2. Consider any LCL problem on bounded degree trees. We prove an automatic-speedup theorem that states that any randomized @math -time algorithm solving the LCL can be transformed into a deterministic @math -time algorithm. Together with a previous result, this establishes that on trees, there are no natural deterministic complexities in the ranges @math --- @math or @math --- @math . 3. We expose a gap in the randomized time hierarchy on general graphs. Any randomized algorithm that solves an LCL problem in sublogarithmic time can be sped up to run in @math time, which is the complexity of the distributed Lovasz local lemma problem, currently known to be @math and @math . This paper addresses the cornerstone family of 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 @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. We consider the distributed message-passing @math model. In this model a communication network is represented by a graph where vertices host processors, and communication is performed over the edges. Computation proceeds in synchronous rounds. The running time of an algorithm is the number of rounds from the beginning until all vertices terminate. Local computation is free. An algorithm is called local if it terminates within a constant number of rounds. The question of what problems can be computed locally was raised by Naor and Stockmeyer [16] in their seminal paper in STOC'93. Since then the quest for problems with local algorithms, and for problems that cannot be computed locally, has become a central research direction in the field of distributed algorithms [9,11,13,17]. We devise the first local algorithm for an NP-complete problem. Specifically, our randomized algorithm computes, with high probability, an O(n1 2+e ·χ)-coloring within O(1) rounds, where e>0 is an arbitrarily small constant, and χ is the chromatic number of the input graph. (This problem was shown to be NP-complete in [21].) On our way to this result we devise a constant-time algorithm for computing (O(1), O(n1 2+e))-network-decompositions. Network-decompositions were introduced by [1], and are very useful for solving various distributed problems. The best previously-known algorithm for network-decomposition has a polylogarithmic running time (but is applicable for a wider range of parameters) [15]. We also devise a Δ1+e-coloring algorithm for graphs with sufficiently large maximum degree Δ that runs within O(1) rounds. It improves the best previously-known result for this family of graphs, which is O(log*n) [19]. The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: There are nontrivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem that can be solved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given time @math . Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs). We present a simple distributed @math -approximation algorithm for maximum weight independent set (MaxIS) in the @math model which completes in @math rounds, where @math is the maximum degree, @math is the number of rounds needed to compute a maximal independent set (MIS) on @math , and @math is the maximum weight of a node. Whether our algorithm is randomized or deterministic depends on the MIS algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in @math rounds, where @math is the number of nodes. We also present a deterministic @math -round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a @math -approximation for maximum weight matching without incurring any additional round penalty in the @math model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of for which we describe a mechanism that allows the simulation to run in the @math model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ( @math ) allows us to devise a distributed algorithm requiring @math rounds for any constant @math . For the unweighted case, we can even obtain a @math -approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on @math . Multiround algorithms are now commonly used in distributed data processing systems, yet the extent to which algorithms can benefit from running more rounds is not well understood. This paper answers this question for a spectrum of rounds for the problem of computing the equijoin of @math relations. Specifically, given any query @math with width @math , intersection width @math , input size @math , output size @math , and a cluster of machines with @math memory available per machine, we show that: (1) @math can be computed in @math rounds with @math communication cost. (2) @math can be computed in @math rounds with @math communication cost. Intersection width is a new notion of queries and generalized hypertree decompositions (GHDs) of queries we introduce to capture how connected the adjacent cyclic components of the GHDs are. We achieve our first result by introducing a distributed and generalized version of Yannakakis's algorithm, called GYM. GYM takes as input any GHD of @math with width @math and depth @math , and computes @math in @math rounds and @math communication cost. We achieve our second result by showing how to construct GHDs of @math with width @math and depth @math . We describe another technique to construct GHDs with longer widths and shorter depths, demonstrating a spectrum of tradeoffs one can make between communication and the number of rounds. We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i.e., an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node @math hears a message from a neighbor @math in a given round, if @math listens in this round, and if @math is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems. What is the shortest labeling scheme that permits topology recognition in all wireless tree networks of diameter @math and maximum degree @math ? What is the fastest topology recognition algorithm working for all wireless tree networks of diameter @math and maximum degree @math , using such a short labeling scheme? We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree @math is @math . For such short schemes, used by an algorithm working for the class of trees of diameter @math and maximum degree @math , we show almost matching bounds on the time of topology recognition: an upper bound @math , and a lower bound @math , for any constant @math . Let G=(V,E) be an n-vertex graph and Md a d-vertex graph, for some constant d. Is Md a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to @math bits. A simple deterministic algorithm that requires @math communication rounds is presented. For the special case that Md is a triangle, we present a probabilistic algorithm that requires an expected @math rounds of communication, where t is the number of triangles in the graph, and @math with high probability. We also present deterministic algorithms that are specially suited for sparse graphs. In graphs of maximum degree Δ, we can test for arbitrary subgraphs of diameter D in @math rounds. For triangles, we devise an algorithm featuring a round complexity of @math , where A denotes the arboricity of G. A central theme in distributed network algorithms concerns understanding and coping with the issue of locality . Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for . In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard @math model of computation and define @math (for local decision ) as the class of decision problems that can be solved in @math communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class @math , containing all languages for which there exists a randomized algorithm that runs in @math rounds, accepts correct instances with probability at least @math and rejects incorrect ones with probability at least @math . We show that @math is a threshold for the containment of @math in @math . More precisely, we show that there exists a language that does not belong to @math for any @math but does belong to @math for any @math such that @math . On the other hand, we show that, restricted to hereditary languages, @math , for any function @math and any @math such that @math . In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide languages . Finally, we introduce the notion of local reduction, and establish some completeness results. We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of and exemplify its strength by proving two new lower bounds for triangle membership in the CONGEST(B) model: (i) Any @math -round algorithm requires @math for a constant @math . (ii) If @math , even in constant-degree graphs any algorithm must take @math rounds. The implication of the former is the first proven separation between the LOCAL and the CONGEST models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for , under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice. In the subgraph-freeness problem, we are given a constant-size graph @math , and wish to determine whether the network contains @math as a subgraph or not. The relaxation of the problem only requires us to distinguish graphs that are @math -free from graphs that are @math -far from @math -free, meaning an @math -fraction of their edges must be removed to obtain an @math -free graph. Recently, Censor-Hillel et. al. and showed that in the property-testing regime it is possible to test @math -freeness for any graph @math of size 4 in constant time, @math rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs @math of size 4 cannot test @math -cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that @math -cycle-freeness, and indeed @math -freeness for many other graphs @math comprising more than 4 vertices, can be tested in constant time. We show that @math -freeness can be tested in @math rounds for any cycle @math , improving on the running time of @math of the previous algorithms for triangle-freeness and @math -freeness. In the special case of triangles, we show that triangle-freeness can be solved in @math rounds independently of @math , when @math is not too small with respect to the number of nodes and edges. We also show that @math -freeness for any constant-size tree @math can be tested in @math rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in @math rounds. This class includes all graphs over 5 vertices except the 5-clique, @math . For cliques @math over @math nodes, we show that @math -freeness can be tested in @math rounds, where @math is the number of edges. We present the best known algorithms for approximating the minimum-size undirected @math -edge connected spanning subgraph. For simple graphs our approximation ratio is @math . The more precise version of this bound requires @math , and for all such @math it improves the long-standing performance ratio of Cheriyan and Thurimella [SIAM J. Comput., 30 (2000), pp. 528-560], @math . The improvement comes in two steps. First we show that for simple @math -edge connected graphs, any laminar family of degree @math sets is smaller than the general bound ( @math versus @math ). This immediately implies that iterated rounding improves the performance ratio of Cheriyan and Thurimella. The second step carefully chooses good edges for rounding. For multigraphs our approximation ratio is @math . This improves the previous ratio @math [H. N. Gabow, M. X. Goemans, E. Tardos, and D. P. Williamson, Networks, 53 (2009), pp. 345-357]. It is of interest since it is known that for some constant @math , an approximation ratio @math implies @math . Our approximation ratio extends to the minimum-size Steiner network problem, where @math denotes the average vertex demand. The algorithm exploits rounding properties of the first two linear programs in iterated rounding. The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to decide whether the Hamming distance between their @math -bit input strings is large (i.e., at least @math ) or small (i.e., at most @math ); they do not care if it is neither large nor small. This @math gap in the problem specification is crucial for capturing the approximation allowed to a data stream algorithm. Thus far, for randomized communication, an @math lower bound on this problem was known only in the one-way setting. We prove an @math lower bound for randomized protocols that use any constant number of rounds. As a consequence we conclude, for instance, that @math -approximately counting the number of distinct elements in a data stream requires @math space, even with multiple (a constant number of) passes over the input stream. This extends earlier one-pass lower bounds, answering a long-standing open question. We obtain similar results for approximating the frequency moments and for approximating the empirical entropy of a data stream. In the process, we also obtain tight @math lower and upper bounds on the one-way deterministic communication complexity of the problem. Finally, we give a simple combinatorial proof of an @math lower bound on the one-way randomized communication complexity. Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an @math vertex graph, and need to output a clique. We show that if the input graph is drawn at random from @math (and hence is likely to have a clique of size roughly @math ), then for every @math and constant @math , there is an @math (that may depend on @math and @math ) such that no algorithm that makes @math probes in @math rounds is likely (over the choice of the random graph) to output a clique of size larger than @math . We study the following one-person game against a random graph process: the Player's goal is to @math -colour a random sequence of edges @math of a complete graph on @math vertices, avoiding a monochromatic triangle for as long as possible. The game is over when a monochromatic triangle is created. The online version of the game requires that the Player should colour each edge as it comes, before looking at the next edge.While it is not hard to prove that the expected length of this game is about @math , the proof of the upper bound suggests the following relaxation: instead of colouring online, the random graph is generated in only two rounds, and the Player colours the edges of the first round before the edges of the second round are thrown in. Given the size of the first round, how many edges can there be in the second round for the Player to be likely to win? In the extreme case, when the first round consists of a random graph with @math edges, where @math is a positive constant, we show that the Player can win with high probability only if constantly many edges are generated in the second round. We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes @math rounds assuming noiseless communication, the goal is to find a coding scheme that takes R' rounds and computes the same function with high probability even when the communication is noisy, while maintaining a constant asymptotic rate, i.e., while keeping n,R→∞ R R' positive. Rajagopalan and Schulman (STOC '94) were the first to consider this question, and provided a coding scheme with rate O(1 log (d+1)), where d is the maximal degree in the network. While that scheme provides a constant rate coding for many practical situations, in the worst case, e.g., when the network is a complete graph, the rate is O(1 log n), which tends to 0 as n tends to infinity. We revisit this question and provide an efficient coding scheme with a constant rate for the interesting case of fully connected networks. We furthermore extend the result and show that if a (d-regular) network has mixing timem, then there exists an efficient coding scheme with rate O(1 m3log m). This implies a constant rate coding scheme for any n-party protocol over a d-regular network with a constant mixing time, and in particular for random graphs with @math vertices and degrees nΩ(1). In the standard CONGEST model for distributed network computing, it is known that "global" tasks such as minimum spanning tree, diameter, and all-pairs shortest paths, consume large bandwidth, for their running-time is @math rounds in @math -node networks with constant diameter. Surprisingly, "local" tasks such as detecting the presence of a 4-cycle as a subgraph also requires @math rounds, even using randomized algorithms, and the best known upper bound for detecting the presence of a 3-cycle is @math rounds. The objective of this paper is to better understand the landscape of such subgraph detection tasks. We show that, in contrast to , which are hard to detect in the CONGEST model, there exists a deterministic algorithm for detecting the presence of a subgraph isomorphic to @math running in a number of rounds, for every tree @math . Our algorithm provides a distributed implementation of a combinatorial technique due to Erd o for sparsening the set of partial solutions kept by the nodes at each round. Our result has important consequences to , i.e., to randomized algorithms whose aim is to distinguish between graphs satisfying a property, and graphs far from satisfying that property. In particular, we get that, for every graph pattern @math composed of an edge and a tree connected in an arbitrary manner, there exists a distributed testing algorithm for @math -freeness, performing in a constant number of rounds. Although the class of graph patterns @math formed by a tree and an edge connected arbitrarily may look artificial, all previous results of the literature concerning testing @math -freeness for classical patterns such as cycles and cliques can be viewed as direct consequences of our result, while our algorithm enables testing more complex patterns. We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in BFM86 ). We then proceed to construct optimal Ramsey partitions, and use them to show that for every @math , every @math -point metric space has a subset of size @math which embeds into Hilbert space with distortion @math . This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor BLMN05 , in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in TZ05 . Namely, we show that for every @math point metric space @math , and @math , there exists an @math -approximate distance oracle whose storage requirement is @math , and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking. We present algorithmic and hardness results for network design problems with degree or order constraints. The first problem we consider is the Survivable Network Design problem with degree constraints on vertices. The objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds @math on the vertices. This includes the well-studied Minimum Bounded Degree Spanning Tree problem as a special case. Our main result is a @math -approximation algorithm for the edge-connectivity Survivable Network Design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex @math is at most @math . This implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the Minimum Bounded Degree Steiner Forest problem. Our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the Minimum Bounded Degree Arborescence problem and the Minimum Bounded Degree Strongly @math -Edge-Connected Subgraph problem. In contrast, we show that the vertex-connectivity Survivable Network Design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. A striking aspect of our algorithmic result is its simplicity. It is based on the iterative relaxation method, which is an extension of Jain's iterative rounding method. This provides an elegant and unifying algorithmic framework for a broad range of network design problems. We also study the problem of finding a minimum cost @math -edge-connected subgraph with at least @math vertices, which we call the @math -subgraph problem. This generalizes some well-studied classical problems such as the @math -MST and the minimum cost @math -edge-connected subgraph problems. We give a polylogarithmic approximation for the @math -subgraph problem. However, by relating it to the Densest @math -Subgraph problem, we provide evidence that the @math -subgraph problem might be hard to approximate for arbitrary @math .