Partition Tolerance and Data Consistency in Structured Overlay Networks

Structured overlay networks forma major class of peer-to-peer systems, which are used to build scalable, fault-tolerant and self-managing distributed applications. This thesis presents algorithms for structured overlay networks, on the routing and data level, in the presence of network and node dynamism. On the routing level, we provide algorithms for maintaining the structure of the overlay, and handling extreme churn scenarios such as bootstrapping, and network partitions and mergers. Since any long lived Internet-scale distributed system is destined to face network partitions, we believe structured overlays should intrinsically be able to handle partitions and mergers. In this thesis, we discuss mechanisms for detecting a network partition and merger, and provide algorithms for merging multiple ring-based overlays. Next, we present a decentralized algorithm for estimating the number of nodes in a peer-to-peer system. Lastly, we discuss the causes of routing anomalies (lookup inconsistencies), their effect on data consistency, and mechanisms on the routing level to reduce data inconsistency. On the data level, we provide algorithms for achieving strong consistency and partition tolerance in structured overlays. Based on our solutions on the routing and data level, we build a distributed key-value store for dynamic partially synchronous networks, which is linearizable, self-managing, elastic, and exhibits unlimited linear scalability. Finally,we present a replication scheme for structured overlays that is less sensitive to churn than existing schemes, and allows different replication degrees for different key ranges that enables using higher number of replicas for hotspots and critical data