Neighbor table construction and update in a dynamic peer-to-peer network

In a system proposed by Plaxton, Rajaraman and Richa (PRR), the expected cost of accessing a replicated object was proved to be asymptotically optimal for a static set of nodes and pre-existence of consistent and optimal neighbor tables in nodes [9]. To implement PRR’s hypercube rout-ing scheme in a dynamic, distributed environment, such as the Internet, various protocols are needed (for node join-ing, leaving, table optimization, and failure recovery). In this paper, we first present a conceptual foundation, called C-set trees, for protocol design and reasoning about con-sistency. We then present the detailed specification of a join protocol. In our protocol, only nodes that are joining need to keep extra state information about the join process. We present a rigorous proof that the join protocol gener-ates consistent neighbor tables for an arbitrary number of concurrent joins. The crux of our proof is based upon in-duction on a C-set tree. Our join protocol can also be used for building consistent neighbor tables for a set of nodes at network initialization time. Lastly, we present both analytic and simulation results on the communication cost of a join in our protocol