Project 2: Chord505, a Simplified Distributed Hash Table

Administrivia

Introduction

You are to design and implement Chord505, a simplified Distributed Hash Table based on Chord. You have been provided with a version of DHT simulator and one of the simplest DHT lookup algorithm implementation, the Ring. This way you can concentrate on designing and implementing your protocol rather than framework issues.

Project description

A DHT lookup algorithm is the foundation of all structured peer-to-peer systems. It provides support for one operation: given a key, it maps the key onto a node. Your goal is to design a scalable lookup algorithm and implement it in the given simulator.

Your main reference should be chord, which provides a relatively simple lookup algorithm. It has the provable scalable property: A lookup only traverses O(log N) nodes. Your design is suggested to be based on chord.

Even with such a reference, a real DHT implementation could be complicated: The nodes can join and leave simultaneously or fail silently; The network could be partitioned. In general, handling byzantine faults is hard. In this project, you do not have to deal with those "churning" effects. In particular, you only have to handle sequential node join and leave. When a node leaves the DHT, it will have the opportunity to notify other relevant nodes about the event.

Doing the project

Students should form programming teams. A programming team should have no more than three people, there will be no exceptions. Notify the TAs by email (cis505@seas.upenn.edu) of your groups. Specify the names and email addresses of the members in your programming team. If you're having trouble forming a group, post a note to the class newsgroup.

Each programming team is required to write a complete implementation of Chord505 DHT. Code sharing between teams is prohibited. If a team contains more than one people, they will receive equal credits whatsoever. (Read as do not complain about your partners.) We do not have design teams in project 2.

We suggest that you stick to the given simulator, but you are free to make any additions that you think improve the simulation process, as long as

1. you document them clearly
2. you clear all changes with us before you implement them.

Grading

1. 30% is based on your submission at the checkpoint. This version of your implementation should support join and, of course, lookup operations. leave and other operations do not have to work at this moment.
2. 40% is based on the correctness and performance of your final implementation. Part of the test cases is given in the release tarball.
3. The remaining 30% is based on your final report. You should design your own test cases to evaluate your implementation. The report should read as a workshop paper format. In the report, we expect to see the design and implementations of your Chord505, as well as the evaluations and lessons you have learned from the project.
4. 15% Extra credits: You can extend the implementation beyond the basic requirement to gain extra credits. Several possible extensions are: (1) Performance enhancement based on network distances. Chord has O(log N) hop performance in the virtual ring. However, the adjacent nodes in the ring may actually be far away in terms of network distance. How to take advantage of network distance information? Read the CFS and i3 papers may give your some ideas. (2) Fault tolerance. The nodes in real life may fail arbitrarily. How does that impact to your DHT implementation? How does network failures impact the DHT as well? (3) Security. What if part of the nodes do not behave according to the protocol, or even maliciously? Other interesting topics are also welcome. Please analysis your new algorithms in a quantitative approach and be explicit about whether the idea is your own or proposed by other people. In the latter case, cite it. Talk to the course staff at least 2 days ahead of the deadline if you think you are doing great stuff and need an extension.