Distributed Hash Tables (DHTs) are useful tools for building large scale distributed systems. DHTs provide a hash-table-like interface to applications by routing a key to its responsible node among the current set of participating nodes. DHT deployments are characterized by churn, a continuous process of nodes joining and leaving the network.

Lookup latency is important to applications that use DHTs to locate data. In order to achieve low latency lookups, each node needs to consume bandwidth to keep its routing tables up to date under churn. A robust DHT should use bandwidth sparingly and avoid overloading the network when the the deployment scenario deviates from design assumptions. Ultimately, DHT designers are interested in obtaining best latency lookups using a bounded amount of bandwidth across a wide range of operating environments. This thesis presents a new DHT protocol, Accordion, that achieves this goal.

Accordion bounds its overhead traffic according to a user specified bandwidth budget and chooses a routing table size that minimizes lookup latency, balancing the need for both low lookup hop-count and low timeout probability. Accordion employs a unique design for managing routing tables. Nodes acquire new routing entries opportunistically through application lookup traffic. Large bandwidth budgets lead to big routing table and low lookup hop-count. Nodes evict entries that are likely dead based on past statistics of node lifetimes. Short node lifetimes lead to high eviction rates and a small routing table with low maintenance overhead. The routing table size is determined by the equilibrium of the neighbor acquisition and eviction processes. Accordion's automatic table size adjustment allows it to bound its bandwidth use and achieve latencies similar or better than existing manually tuned protocols across a wide range of operating environments.