Linked decompositions of networks and the power of choice in Polya urns
Henry Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou · 2008
A linked decomposition of a graph with n nodes is a set of subgraphs covering the n nodes such that all pairs of subgraphs intersect; we seek linked decompositions such that all subgraphs have about n vertices, loga-rithmic diameter, and each vertex of the graph belongs to either one or two subgraphs. A linked decomposition enables many control and management functions to be implemented locally, such as resource sharing, mainte-nance of distributed directory structures, deadlock-free routing, failure recovery and load balancing, without requiring any node to maintain information about the state of the network outside the subgraphs to which it belongs. Linked decompositions also enable efficient routing schemes with small routing tables, which we de-scribe in Section 5. Our main contribution is to show that “Internet-like graphs ” (e.g. the preferential attach-ment model proposed by Barabasi et al. [11] and other similar models) have linked decompositions with the pa-rameters described above with high probability; more-over, our experiments show that the Internet topology itself can be so decomposed. Our proof proceeds by an-alyzing a novel process, which we call Polya urns with the power of choice, which may be of great independent interest. In this new process, we start with n nonempty bins containing O(n) balls total, and each arriving ball is placed in the least loaded of m bins, drawn indepen-dently at random with probability proportional to load. Our analysis shows that in our new process, with high probability the bin loads become roughly balanced some