has recently been identified as a key to the modular design of efficient network algorithms . Using this method as a basic building block leads to significant performance improvements for several fundamental network control problems (such as shortest paths , job scheduling and load balancing [8], broadcast and multicast [4], routing with small tables [11], deadlock prevention [7], bandwidth management in high-speed networks [5], and database management [14]), as well as for classical problems in sequential computing (such as finding small edge cuts in planar graphs and approximate all-pairs shortest paths ). In most of these applications, sparse neighborhood covers yield a polylogarithmic-overhead solution to the problem. Thus, in a sense, the impact of efficient sparse neighborhood cover algorithms on distributed network algorithms is analogous to the impact of efficient data structures (such as balanced search trees or 2-3 trees) on sequential computation.
In parallel to the introduction of sparse neighborhood covers in , the strongly related, yet distinct, notion of network decomposition was introduced in . The main difference between the two notions is that sparse neighborhood covers, as used in [7-10, 14, 20], consist of clusters that capture the expected definition of local neighborhood (see Section 2), while network decomposition as utilized in employs only a weak notion of neighborhood. In fact, the way network decomposition is defined in [5], the clusters might not even be internally connected. For many applications in distributed computing, the stronger notion of sparse covers is essential. For example, decompositions based on the network decomposition structure introduced in [6] are not sufficient to support local routing, where the path between two vertices in the same cluster should consist entirely of vertices within that cluster. Notable exceptions for which such a decomposition suffices are those applications based on ''symmetry-breaking''; i.e., such a decomposition can be used to construct a maximal independent set or a (โฌ ฯฉ 1) coloring (where โฌ is the maximum vertex degree in the graph) fast in the distributed domain .
The goal of this paper is to define fast distributed algorithms for both high-quality network decomposition and sparse neighborhood covers.