A Hypercube-based Peer-to-Peer Data Store Resilient against Peer Population Fluctuation

These days many people, when hearing the term Peer-to-Peer network (P2PN), think of unrestricted and potentially illegal ``file-sharing'' on the Internet. In traditional P2PN usually a limited number of peers make a set of files available. These files become inaccessible when those peers leave the network. Furthermore inevitable fluctuation of the peer population makes the attainment of a specific quality of service in terms of correct and complete file downloads hard or even impossible. In what follows the author also wants to foster the emerging conception that the concept of Peer-to-Peer networks has much more potential than simple file-sharing.In the focus of this dissertation are the problems caused and aggravated by peer population fluctuation. Starting from an analysis of the problems in 2nd generation P2PN, the author expounds his own definition and approach to a Peer-to-Peer data store (P2PD) that, in contrast to a pure P2PN, stores data items, once inserted, reliably with high probability. The P2PD of the author offers the following unique selling points in comparison with related P2PN:Instead of a single peer being responsible for availability, accessibility, and security of a set of data items, a group of peers is. The author calls such a group a ``replication group'' because all peers belonging to such a group store an identical copy of the group's set of data items. Peer joins and leaves thus affect the availability of data items much less than they would in 2nd generation P2PN.In the author's P2PD, virtual links enable communication and data transfer among peers in different replication groups. These links are designed to be redundant so that the P2PD remains connected and does not partition with high probability.The P2PD of the author supports three data consistency models in order to better serve applications from different domains with diverse requirements.Starting with the analysis of requirements from different application domains, the author set out to design and describe his P2PD with a reference model for P2PN followed by implementing his P2PD for simulation. To predict the theoretical lookup performance, given the size of and fluctuation rate in the P2PD, the author used probability theory to analyze the lookup operation. Two other theoretical models aim at analyzing and determining optimal points in time for executing maintenance operations that counter peer population fluctuation. With the first maintenance operation, coalesce, two replication groups can be merged to maintain data availability in case the peer population shrinks. With the opposite maintenance operation, split, a replication group can be divided into two sibling groups in the event that the peer population grows and economic maintenance of the original group becomes impossible.To validate the theoretical models, numerous simulation experiments were conducted. First of all, experiments served to verify the correctness of the P2PD simulation model implementation. In a second step, the author compared theoretical results predicting lookup reliability and performance under various conditions with those obtained from simulation runs. With an additional string of experiments the coalesce operation was validated and shown that fusions of any two sibling groups succeed with high probability provided the fluctuation rate does not exceed an upper bound. With the third string of experiments the theoretical model of the split operation was validated. Finally, the author compared the lookup performance and resilience against peer population fluctuation of some well-known 2nd generation P2PN with those of his own P2PD.