Comparing the performance of distributed hash tables under churn

Jinyang Li, Jeremy Stribling, Thomer M. Gil, Robert Morris, M. Frans Kaashoek

Research output: Contribution to journalConference articlepeer-review


A protocol for a distributed hash table (DHT) incurs communication costs to keep up with churn - changes in membership - in order to maintain its ability to route lookups efficiently. This paper formulates a unified framework for evaluating cost and performance. Communication costs are combined into a single cost measure (bytes), and performance benefits are reduced to a single latency measure. This approach correctly accounts for background maintenance traffic and timeouts during lookup due to stale routing data, and also correctly leaves open the possibility of different preferences in the tradeoff of lookup time versus communication cost. Using the unified framework, this paper analyzes the effects of DHT parameters on the performance of four protocols under churn.

Original languageEnglish (US)
Pages (from-to)87-99
Number of pages13
JournalLecture Notes in Computer Science
StatePublished - 2004
EventThird International Workshop on Peer-to-Peer Systems, IPTPS 2004 - La Jolla, CA, United States
Duration: Feb 26 2004Feb 27 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Comparing the performance of distributed hash tables under churn'. Together they form a unique fingerprint.

Cite this