Local Computation
Authors:
Top Cited Papers
Open Access
- 31 March 2016
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 63 (2) , 1-44
Abstract
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.Keywords
This publication has 36 references indexed in Scilit:
- Survey of local algorithmsACM Computing Surveys, 2013
- Bounds on contention management algorithmsTheoretical Computer Science, 2011
- Hundreds of impossibility results for distributed computingDistributed Computing, 2003
- Explicit construction of graphs with an arbitrary large girth and of large sizeDiscrete Applied Mathematics, 1995
- Low diameter graph decompositionsCombinatorica, 1993
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Deterministic coin tossing with applications to optimal parallel list rankingInformation and Control, 1986
- A fast and simple randomized parallel algorithm for maximal matchingInformation Processing Letters, 1986
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974