Research Article
Key-Based Consistency and Availability in Structured Overlay Networks
@INPROCEEDINGS{10.4108/ICST.INFOSCALE2008.3537, author={Tallat M. Shafaat and Monika Moser and Thorsten Sch\'{y}tt and Alexander Reinefeld and Ali Ghodsi and Seif Haridi}, title={Key-Based Consistency and Availability in Structured Overlay Networks}, proceedings={3rd International ICST Conference on Scalable Information Systems}, publisher={ICST}, proceedings_a={INFOSCALE}, year={2010}, month={5}, keywords={DHTs Key availability Lookup consistency}, doi={10.4108/ICST.INFOSCALE2008.3537} }- Tallat M. Shafaat
Monika Moser
Thorsten Schütt
Alexander Reinefeld
Ali Ghodsi
Seif Haridi
Year: 2010
Key-Based Consistency and Availability in Structured Overlay Networks
INFOSCALE
ICST
DOI: 10.4108/ICST.INFOSCALE2008.3537
Abstract
Structured Overlay Networks provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. Structured overlays provide lookup services that map keys to nodes that can be used as processing or storage resources. The lookups for a key may return inconsistent results. Consequently, it is nontrivial to provide consistent data services on the top of structured overlays that are built on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the effect of lookup inconsistencies can be reduced by assigning responsibility of key intervals to nodes. We present our results as a trade-off between consistency and availability of keys. Further, since many distributed applications employ quorum techniques at their core, we analyze the probability that majority-based quorum techniques will function correctly in a structured overlay with inconsistent lookups. Our analysis shows that the probability of majority-based algorithms to function correctly despite lookup inconsistencies is high.