Donut is an implementation of an available, replicated distributed hash table built on top of Chord. The design was built to support storage of common file sizes in a closed cluster of systems. This paper discusses the two layers of the implementation and a discussion of future development. First, we discuss the basics of Chord as an "overlay network" and our implementation details, second, Donut as a hash table providing availability and replication and thirdly how further development towards a distributed file system may proceed.

Paper: Donut: A Robust Distributed Hash Table based on Chord

Slide Deck: Donut


Done for CSE 490H (Distributed Capstone) at University of Washington.


Mentors (Google):
  • Arunabha Ghosh
  • Jeff Carollo


  1. Proposal
  2. Chord Implementation
    1. Introduction
    2. Terms
    3. Basic design
    4. Joins
    5. Stabilize, Notify, Fix Fingers and Check Predecessor
    6. Leaves and Successor Lists
  3. Hashtable Implementation
    1. Interface
    2. Replication
  4. Furture Directions
  5. References