Peer-to-Peer Algorithms for Sampling Generic Topologies

You are cordially invited to attend the PhD Dissertation Defense of Cyrus HALL on Thursday, April 29th 2010 at 13h30 in room CC-250 (Main building)

ABSTRACT:

Peer sampling is a fundamental building block of peer-to-peer networking, used to implement search, replication, and monitoring schemes.  Yet existing peer-sampling algorithms suffer from one or more of the following problems: they require specially constructed topologies (e.g., gossip peer tables), are hard to parameterize correctly and efficiently (e.g., finding the minimal sample walk length), or do not offer precise statistical guarantees (e.g., independent and identically-distributed samples).  This thesis proposes two distributed algorithms to address these problems.

The first algorithm assigns the link transition probabilities of a peer-to-peer network such that a random walk can sample peers uniformly.Using local operations, peers quickly converge to an assignment of probability such that the transition probability matrix representing the entire network is doubly stochastic, a property that guarantees that the sampling distribution is uniform.

The second algorithm estimates the largest magnitude eigenvalues of a peer-to-peer network, which are directly related to the necessary length of a sample walk.  It models the peer-to-peer network as a linear dynamic system defined by the transition probability matrix.  The algorithm calculates the impulse response of the dynamic system using an efficient local process.  The resulting impulse is then used to realize a rank-reduced approximation of the global system at each peer in the network.  The high magnitude eigenvalues of this approximation closely match the eigenvalues of the full linear system.  This allows for the on-line parameterization of sampling algorithms, such that they can use the fewest hops necessary to sample with the desired precision.

We evaluate both algorithms using analytical and experimental methods, and find them to perform adequately across a wide-range of topologies commonly used to model peer-to-peer networks.  The results of our analysis indicate that it is possible to create generic sampling algorithms that sample from a known and useful target distribution, while also supporting on-line parameterization.

DISSERTATION COMMITTEE:

• Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Fernando Pedone, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Robbert van Renesse, Cornell University, USA (External Member)