Shelley Zhuang and Ion Stoica and Randy Katz

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-05-1394

, 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1394.pdf

Distributed Hash Tables (DHTs) support a hash-table-like lookup interface: given a key, it maps the key onto a node. One of the crucial questions facing DHTs is whether lookups can route correctly in a dynamic environment where the routing state is inconsistent. The routing state may become inconsistent when a node falsely thinks a failed neighbor is up (false negative), when a node falsely removes a neighbor that is up (false positive), when a new node joins but has not been fully incorporated into the routing state (join hole), and when a node leaves and disrupts the routing state (leave recovery). In this paper we analyze the cost of inconsistency in DHTs. Using the example of Chord, we evaluate the cost of each type of inconsistency on lookup performance. We find that the routing invariant has a first order impact on the relative cost of different types of inconsistencies. In addition, the cost of false negatives is higher than that of false positives, which means it is more important to ensure timely failure detection than a low probability of false positives. The cost of join holes and leave recoveries are also higher than that of false positives due to the routing invariant of Chord. We also make conjectures about the cost of inconsistency in other DHTs based on their routing invariants.

---

BibTeX citation:

@techreport{Zhuang:CSD-05-1394,
    Author= {Zhuang, Shelley and Stoica, Ion and Katz, Randy},
    Title= {The Cost of Inconsistency in DHTs},
    Year= {2005},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5652.html},
    Number= {UCB/CSD-05-1394},
    Abstract= {Distributed Hash Tables (DHTs) support a hash-table-like lookup interface: given a key, it maps the key onto a node. One of the crucial questions facing DHTs is whether lookups can route correctly in a dynamic environment where the routing state is inconsistent. The routing state may become inconsistent when a node falsely thinks a failed neighbor is up (false negative), when a node falsely removes a neighbor that is up (false positive), when a new node joins but has not been fully incorporated into the routing state (join hole), and when a node leaves and disrupts the routing state (leave recovery). In this paper we analyze the cost of inconsistency in DHTs. Using the example of Chord, we evaluate the cost of each type of inconsistency on lookup performance. We find that the routing invariant has a first order impact on the relative cost of different types of inconsistencies. In addition, the cost of false negatives is higher than that of false positives, which means it is more important to ensure timely failure detection than a low probability of false positives. The cost of join holes and leave recoveries are also higher than that of false positives due to the routing invariant of Chord. We also make conjectures about the cost of inconsistency in other DHTs based on their routing invariants.},
}

EndNote citation:

%0 Report
%A Zhuang, Shelley 
%A Stoica, Ion 
%A Katz, Randy 
%T The Cost of Inconsistency in DHTs
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1394
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5652.html
%F Zhuang:CSD-05-1394