A peer-to-peer (P2P) system is a networked system characterized by the lack of centralized control, in which all or most communication is symmetric. Also, a P2P system is supposed to handle frequent arrivals and departures of nodes, and is expected to scale to very large network sizes. These requirements make the design of P2P systems particularly challenging.
We investigate two central issues pertaining to the design of P2P systems: load balancing and routing. In the first part of this thesis, we study the problem of load balancing in the context of Distributed Hash Tables (DHTs). Briefly, a DHT is a giant hash table that is maintained in a P2P fashion: Keys are mapped to a hash space I --- typically the interval [0,1), which is partitioned into blocks among the nodes, and each node stores the keys that are mapped to its block. Based on the position of their
blocks in I, the nodes also set up connections among themselves, forming a routing network, which facilitates efficient key location.
Typically, in a DHT it is desirable that the nodes' blocks are roughly of equal size, since this usually implies a balanced
distribution of the load of storing keys among nodes, and it also simplifies the design of the routing network. We propose and analyze a simple distributed scheme for partitioning I, inspired by the multiple random choices paradigm. This scheme guarantees that, with high probability, the ratio between the largest and smallest blocks
remains bounded by a small constant. It is also message efficient, and the arrival or departure of a node perturbs the current
partition of I minimally. A unique feature of this scheme is that it tolerates adversarial arrivals and departures of nodes.
In the second part of the thesis, we investigate the complexity of a natural decentralized routing protocol, in a broad family of randomized networks. The network family and routing protocol in question are inspired by a framework proposed by Kleinberg to model small-world phenomena in social networks, and they capture many
designs that have been proposed for P2P systems. For this model we establish a general lower bound on the expected message complexity of routing, in terms of the average node degree. This lower bound almost matches the corresponding known upper bound.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/17462 |
| Date | 15 July 2009 |
| Creators | Giakkoupis, George |
| Contributors | Hadzilacos, Vassos |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0036 seconds