Ranch: a dynamic network topology

Peer-to-peer computing is an emerging paradigm that has the potential of harnessing enormous amounts of under-utilized computational resources (e.g., home computers). A central problem in peer-to-peer computing is how to organize the network nodes so that sophisticated applications can be efficiently supported. The cornerstone of a peer-to-peer network is a dynamic network topology that determines the neighbor relationships to be maintained by the network nodes. This dissertation is concerned with algorithmic and concurrency issues in dynamic network topologies. We present Ranch (random cyclic hypercube), a simple, recursive topology consisting of a collection of rings. Ranch is a scalable topology. In particular, it has logarithmic in-degree, out-degree, and diameter, and it uses only a logarithmic number of messages for a node to join or leave the network. Ranch also has a number of additional desirable properties, including locality awareness and fault tolerance. We show how to build a name resolution scheme for Ranch that enables the peer-topeer network to find data items efficiently. Our results include a name replication scheme and a fault-tolerant lookup algorithm. We address the problem of topology maintenance in peer-to-peer networks, that is, how to properly update the neighbor variables when nodes join and leave the network, possibly concurrently. We design, and prove the correctness of, protocols that maintain the ring topology, the basis of several peer-to-peer networks, in the fault-free environment. Our protocols handle both joins and leaves actively (i.e., they update the neighbor variables as soon as a join or a leave occurs). We use an assertional method to prove the correctness of our protocols, that is, we first design a global invariant for a protocol and then show that every action of the protocol preserves the invariant. Our protocols are simple and our proofs are rigorous and explicit. We extend our results on the maintenance of rings to address the maintenance of Ranch. We present active and concurrent maintenance protocols that handle both joins and leaves for Ranch, along with their assertional correctness proofs. The protocols for Ranch use the protocols for rings as a building block. The protocols and the correctness proofs for Ranch substantially extend those for rings. We present simulation results that demonstrate the scalability and locality awareness of Ranch.