Change search
ReferencesLink to record
Permanent link

Direct link
Partition Tolerance and Data Consistency in Structured Overlay Networks
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Structured overlay networks form a 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 scenariossuch 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 discussthe 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.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. , ix, 164 p.
Trita-ICT-ECS AVH, ISSN 1653-6363 ; 13:09
Keyword [en]
Structured overlay networks, distributed Hash tables, network partitions and mergers, size estimation, lookup inconsistencies, distributed key-value stores, linearizability, dynamic reconfiguration, replication.
National Category
Computer Systems
Research subject
URN: urn:nbn:se:kth:diva-122082ISBN: 978-91-7501-725-9OAI: diva2:620656
Public defence
2013-06-03, Sal/Hall D, Forum, KTH-ICT, Isafjordsgatan 39, Kista, 13:00 (English)

QC 20130515

Available from: 2013-05-15 Created: 2013-05-09 Last updated: 2013-05-15Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Tallat Mahmood, Shafaat
By organisation
Software and Computer systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 363 hits
ReferencesLink to record
Permanent link

Direct link