3rd International ICST Conference on Scalable Information Systems

Research Article

Key-Based Consistency and Availability in Structured Overlay Networks

Download671 downloads
        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},
        keywords={DHTs Key availability Lookup consistency},
  • 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
    DOI: 10.4108/ICST.INFOSCALE2008.3537
Tallat M. Shafaat1,*, Monika Moser2,*, Thorsten Schütt2,*, Alexander Reinefeld2,*, Ali Ghodsi3,*, Seif Haridi3,*
  • 1: Royal Institute of Technology (KTH), Stockholm, Sweden
  • 2: Zuse Institute Berlin, Berlin, Germany
  • 3: Swedish Institute of Computer Science, Stockholm, Sweden
*Contact email: tallat@kth.se, moser@zib.de, schuett@zib.de, ar@zib.de, ali@sics.se, seif@sics.se


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.