Local Computation: Lower and Upper Bounds

Understand

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.