Back to search

Athens University Economics and Business (AUEB)

Εφαρμογή θεωρίας αλγορίθμων στο διαδίκτυο

Abstract

dc:description

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 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 × 12

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/19637

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Amanatidis, Christos; Αμανατίδης, Χρήστος. Εφαρμογή θεωρίας αλγορίθμων στο διαδίκτυο. Athens University Economics and Business (AUEB), 2009. http://hdl.handle.net/10442/hedi/19637