This assignment is to be done either individually or in pairs. Do not show your code to any other group and do not look at any other group's code. Do not put your code in a public directory or otherwise make it public. However, you may get all the help you need from the TAs or the instructor. You are encouraged to use the WebCT Discussions page to post questions so that other students can also answer/see the answers.

A Consistent-Hashing Fault-Tolerant Distributed Hashtable

The goal of this assignment is to implement in SALSA, a fault-tolerant distributed hashtable such as Chord, capable of dealing with dynamic node additions, sequential node failures, and concurrent addition, update, and removal of key/value pairs.

Part 1 (50%): A Distributed Hashtable

You are to create a behavior Node.salsa which takes four parameters as arguments: the logarithm of the maximum number of nodes in the hashtable (from here on n), the node's id, its UAN, and the UAN of an actor to connect to in the distributed hashtable. If there is no actor to connect to, this is the initial node of the distributed hashtable. Each node must support the following message handlers:

• void add(long key, Object value), which adds a key/value pair to the distributed hashtable.
• Object get(long key), which gets the value for a given key in the distributed hashtable.
• Object remove(long key), which removes the key/value pair from the distributed hashtable.
• void update(long key, Object value), which updates the key/value pair in the distributed hashtable.

The get method must operate in logarithmic space and time complexity. That is, the finger table must be of size n and the number of hops to satisfy a lookup must grow proportional to n.

You can assume keys are long numbers, and you can use the mod 2ⁿ hashing function to get a ring identifier in the proper range.

Additionally, write behaviors Add.salsa, Get.salsa, Remove.salsa and Update.salsa, for actors that take the UAN of a node in the distributed hashtable and the corresponding parameters and send the appropriate message to a node in the distributed hashtable and return the result if there is one.

Using the distributed hashtable should look like the following:
 --> salsa Node 8 1 uan://.../node_1
 --> salsa Node 8 136 uan://.../node_136 uan://.../node_1
 --> salsa Node 8 35 uan://.../node_35 uan://.../node_1
 --> salsa Add uan://.../node_1 291 "hello"
 Added "hello" to hashtable with key 291, hash 35, node 35.
 --> salsa Node 8 99 uan://.../node_99 uan://.../node_136
 --> salsa Add uan://.../node_99 15 "world"
 Added "world" to hashtable with key 15, hash 15, node 35.
 --> salsa Node 8 32 uan://.../node_8 uan://.../node_35
 --> salsa Get uan://.../node_35 15
 Retrieved "world" from the hashtable.
 --> salsa Get uan://.../node_136 291
 Retrieved "hello" from the hashtable.
 --> salsa Remove uan://.../node_136 291
 Removed "hello" with key 291 from the hashtable.
 --> salsa Get uan://.../node_1 291
 No key/value pair for key 291 was found in the hashtable.
 --> salsa Update uan://.../node_99 15 "hello"
 Updated value for key 15 to "hello".
 --> salsa Get uan://.../node_35 15
 Retrieved "hello" from the hashtable.

Part 2 (50%): A Soft Fault-Tolerant Distributed Hashtable

When a key/value pair is added to the hashtable, it must be replicated once at another node in the hashtable. In addition, each node must be able to accept a void failure() message. When a node receives a failure message it must remove itself from the distributed hashtable and then the distributed hashtable must replicate all key/value pairs lost by the failure of that node (by using the replicated key/value pairs). You can assume that failure messages will not happen concurrently, i.e., another failure message will not occur until the distributed hashtable has stabilized (replication of key/value pairs and restoration of finger tables have occurred).

Extra Credit Options (10% bonus if working individually, at least one required for full credit if working in a pair):

Option 1:
Instead of duplicating key/value pairs as in part 2, your hashtable must accept a replication parameter r. When a key/value pair is added to the hashtable, it is replicated r times. Include the three following graphs and a short discussion of these results.

• A graph of lookup time vs r, for n = 10, 100 and r = 1..5;
• A graph of addition time vs r, for n = 10, 100 and r = 1..5;
• A graph of failure recovery time vs r, for n = 10, 100 and r = 1..5;

Option 2:
Your distributed hashtable must be able to handle (non-concurrent) hard failures of nodes. A node could be terminated using Ctrl-C or a power off of the machine hosting the node and the distributed hashtable must be able to recover and still accept add/get/update/remove messages.

References:
SALSA Homepage
Chord Homepage
Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications

Due Date:

Received Time	Grade Modification
before Monday, November 7th, 11:59PM	+10%
Tuesday, November 8th, from 12:00AM to 11:59PM	no modification (on time)
Wednesday, November 9th, from 12:00AM to 11:59PM	-10%
from Thursday, November 10th, 12:00AM to Friday, November 11st, 11:59PM	-25%
after Friday, November 11th, 12:00AM	not accepted

The assignment will be graded mostly on correctness, but code clarity / readability will also be a factor (comment, comment, comment!). Be sure your solutions are robust.

Submission Requirements: Your code should consist of a ZIP file containing a README file and two subdirectories part1 and part2. Use your WebCT user name(s) as the filename, either userid1.zip or userid1_userid2.zip. Only submit one assignment per pair (the other does not need to submit anything via WebCT). Please submit your file via WebCT.