The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a distributed fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first polylogarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition, we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, whereas for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks. directly communicate only to a small number of neighboring nodes. For instance, most human communication is between acquaintances or within the family, and neurons are directly linked with merely a relatively small number of other neurons. On the other hand, despite each node being inherently "near-sighted," that is, restricted to local communication, the entirety of the system is supposed to work towards some kind of global goal, solution, or equilibrium. In this work we investigate the possibilities and limitations of local computation, that is, to what degree local information is sufficient to solve global tasks. Many tasks can be solved entirely locally, for instance, determining how many friends of friends one has. Clearly, only local communication is required to answer this question. Many other tasks are inherently global, for instance, counting the total number of nodes or determining the diameter of the system. To solve such global problems, some information must traverse across the entire network. Are there natural tasks that are in the middle of these two extremes, tasks that are neither completely local nor inherently global? In this paper we answer this question affirmatively. Assume, for example, that the nodes want to organize themselves; some nodes should be masters, and the others will be slaves. The rules are that no two masters shall be direct neighbors, but every slave must have at least one master as a direct neighbor. In graph theory, this problem is known as the maximal independent set (MIS) problem. At first, this problem seems local since the rules are completely local. Consequently one might hope for a solution where each node can communicate with its neighbors a few times, and together they can decide who will become master and who will become slave. However, as we show in this article, this intuition is misleading. Even though the problem can be defined in a purely local way, it cannot be solved using local information only! No matter how the system tackles the problem, no matter what protocol or algorithm the nodes use, nonlocal information is vital to solve the task. On the other hand, the problem is also not global: Midrange information is enough to solve the problem. As such the MIS problem establishes an example that is neither local nor global, but in between these extremes. As it turns out to be polylogarithmic in the number of nodes, we call it polylog-local. Using locality-preserving reductions, we are able to show that there exists a whole class of polylog-local problems. We show that this class of polylog-local problems also includes approximation variants of various combinatorial optimization problems, such as minimum vertex cover, minimum dominating set, or maximum matching. In such problems, each node must base its decision (for example, whether to join the dominating set) only on information about its local neighborhood, and, yet, the goal is to collectively achieve a good approximation to the globally optimal solution. Studying such local approximation algorithms is particularly interesting because it sheds light on the tradeoff between the amount of available local information and the resulting global optimality. Specifically, it characterizes the amount of information needed in distributed decision making: what can be done with the information that is available within some fixed-size neighborhood of a node. Positive and negative results for local algorithms can thus be interpreted as information-theoretic upper and lower bounds; they give insight into the value of information. We believe that studying the fundamental possibilities and limitations of local computation is of interest to theoreticians in approximation theory, distributed computing, and graph theory. Furthermore, our results may be of interest for a wide range of scientific areas, for instance, dynamic systems that change over time. Our theory shows that small changes in a dynamic system may cause an intermediate (or polylog-local) "butterfly effect," and it gives nontrivial bounds for self-healing or self-organizing systems, such as self-assembling robots. It also establishes bounds for further application areas, initially in engineering and computing, possibly extending Local Computation: Lower and Upper Bounds 17:3 to other areas studying large-scale systems, for example, social science, finance, neural networks, or ant colonies. Local Computations: We consider a distributed system in which distributed decision makers at the nodes of a graph must base their computations and decisions on the knowledge about their local neighborhoods in the graph. Formally, we are given a graph G = (V, E), |V | = n, and a parameter k (k might depend on n or some other property of G). At each node v ∈ V there is an independent agent (for simplicity, we identify the agent at node v with v as well). Every node v ∈ V has a unique identifier id(v) 1 and possibly some additional input. We assume that each node v ∈ V can learn the complete neighborhood k (v) up to distance k in G (see below for a formal definition of k (v)). Based on this information, all nodes need to make independent computations and need to individually decide on their outputs without communicating with each other. Hence, the output of each node v ∈ V can be computed as a function of its k neighborhood k (v). Synchronous Message Passing Model: The described graph-theoretic local computation model is equivalent to the classic message passing model of distributed computing generally known as the LOCAL model [Peleg 2000; Linial 1992 ]. In this model, the distributed system is modeled as a point-to-point communication network, described by an undirected graph G = (V, E), in which each vertex v ∈ V represents a node (host, device, processor, . . .) of the network, and an edge (u, v) ∈ E is a bidirectional communication channel that connects the two nodes. Initially, nodes have no knowledge about the network graph; they only know their own identifier and potential additional inputs. All nodes wake up simultaneously and computation proceeds in synchronous rounds. In each round, every node can send one arbitrarily long message to each of its neighbors. Since we consider point-to-point networks, a node may send different messages to different neighbors in the same round. Additionally, every node is allowed to perform local computations based on information obtained in messages of previous rounds. Communication is reliable, that is, every message that is sent during a communication round is correctly received by the end of the round. An algorithm's time complexity is defined as the number of communication rounds until all nodes terminate. 2 The LOCAL model defined above is the strongest possible model when studying the impact of locally restricted knowledge on computability, because it focuses entirely on the locality of distributed problems and abstracts away other issues arising in the design of distributed algorithms (e.g., need for small messages, fast local computations, congestion, asynchrony, and packet loss). It is thus the most fundamental model for proving lower bounds on local computation [Linial 1992], because any lower bound is a true consequence of locality restrictions. There is a one-to-one correspondence between the time complexity of distributed algorithms in the LOCAL model and the graph-theoretic notion of neighborhood information. In particular, a distributed algorithm with time complexity k (i.e., in which each node performs k communication rounds) is equivalent to a scenario in which distributed decision makers at the nodes of a graph must base their decision on (complete) knowledge about their k-hop neighborhood k (v) only. This is true because, with unlimited sized 1 All our results hold for any possible ID space including the standard case where IDs are the numbers 1, . . . , n. 2 Notice that this synchronous message passing model captures many practical systems, including for example, Google's Pregel system, a practically implemented computational model suitable for computing problems in large graphs [Malewicz et al. 2010 ].
On the other hand, Kuhn et al. REF showed a lower bound of Ω(min{ log n/ log log n, log ∆/ log log ∆}), even for the LOCAL model.
Local Computation: Lower and Upper Bounds
JACM
Computer Science