Change search
ReferencesLink to record
Permanent link

Direct link
Partition Tolerance and Data Consistency in Structured Overlay Networks
RISE, Swedish ICT, SICS, Computer Systems Laboratory. School of Information and Communication Technology.
Number of Authors: 1
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
2013, 11.
SICS dissertation series, ISSN 1101-1335
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-24222ISBN: 978-91-7501-725-9 (print)OAI: diva2:1043302
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2016-10-31

Open Access in DiVA

fulltext(2253 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 2253 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Computer Systems Laboratory
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
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: 7 hits
ReferencesLink to record
Permanent link

Direct link