Athens University Economics and Business (AUEB)
Εφαρμογή θεωρίας αλγορίθμων στο διαδίκτυο
Abstract
dc:descriptionA 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 square of root of n vertices, logarithmic 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, maintenance 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. Our main contribution is to show that ``Internet-like graphs'' (e.g. The preferential attachment model proposed by Barabasi and other similar models) have linked decompositions with the parameters described above with high probability; moreover, our experiments show that the Internet topology itself can be so decomposed. Our proof proceeds by analyzing 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 independently 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 time beforeO(n2+ε) further balls have arrived and stay roughly balanced, regardless of how the initial O(n) balls were distributed, where ε > 0 can be arbitrarily small, provided m is large enough. We also prove that if all bins start with at least c balls, then with high probability the bin loads become roughly balanced some time before O(n2), provided c is large enough.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Amanatidis, Christos
- Αμανατίδης, Χρήστος
Subjects
dc:subject × 12Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/19637