  The question of what can be computed, and how efficiently, are 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
\emph{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 poly-logarithmic 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, 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.
