CSCI319 Chord System

Programming task:

The Chord system is a structured peer-to-peer network architecture realizing a scalable distributed hash table. In Chord, the peers are organized as a ring. A position within Chord which is held by a computing node is called an index node or simply a peer. Each index node has a finger table and, in addition, holds data items associated with its own key value (its ID within the ring) and any other data items associated with keys larger than the previous index node in the Chord ring

To succeed with this programming task, you will need to understand the Chord system very well! Do not commence the programming task until you have developed a solid understanding of the Chord system. You may need to study the lecture notes, the relevant paragraphs in the text book, and relevant internet sources in order to acquire the level of understanding of CHORD required for this assignment. Commence the work on this assignment once you are confident to have understood how CHORD works.

Your task is to write a simulation of the Chord system on a single computer as a single (non-parallelized, not multi-threaded) process. We will keep this task as simple as possible. The main objectives are:

• to understand how the nodes in Chord communicate.
• to understand how nodes are managed (added/removed) from the system.
• to understand the effects of adding and removal of index nodes.
• to understand how the finger table is computed and maintained.
• to understand how memory utilization and data distribution takes place in Chord.
• to understand how searching is done efficiently in Chord.
• to understand why CHORD is a such a fast and efficient algorithm.
• to understand the concept of scalable algorithms and fast code.

To keep the task as simple as possible, you are to write a single-threaded simulation (i.e. no additional threads are to be created during runtime). Follow the following guidelines:

Develop data structures which are suitable to hold required information for each peer in a CHORD system. Note that index nodes can hold (and access) local information only (I.e, an index nodes never knows of all the other index nodes in a CHORD). Remember that your implementation is to simulate a distributed system. Thus, do not make use of any global variables!

On the basis of the data structures developed by you, write a single threaded (single process) simulation in either C, C++, or Java of the Chord system with the following functions (this is the minimum requirement). You may introduce any number of functions in addition to those stated here:

InitChord(n,...): Create and initialize a new Chord system of size 2ⁿ.You can assume that the parameter n is a positive valued integer whose value is limited to 1 <= n <= 32. Thus, the smallest CHORD that can be created by this function is of size 2, and the largest CHORD is 2³¹. Note that in general the size of a Chord is commonly larger than the number of available index nodes. An example: The CHORD shown in the lecture notes "Architectures" was of size 2⁴but consisted of only 5 peers.

This function will also print your name and student number to the screen (print to standard output). Normally, in a real world CHORD, when a new CHORD is created than there will be at least one index node (the node which created the CHORD will become the first index node in the system), and the new node would assume a random location within CHORD. We will simulate this by creating a new index node at location 0 (zero) within the ring as part of this InitChord(.) function. The size of the finger table for this peer (and any other peer that may be added later) is equal to n.

If InitChord(.) is called more than once (i.e. when there is already a Chord when InitChord is called again) then this function will completely remove the previous CHORD from memory then initialize a new Chord system. The removing of a pre-existing CHORD requires the removal of all its associated peers from the system and the release of all allocated memory (in case of a C or C++ implementation).

The value of parameter n is obtained from a script file (see example below).

AddPeer(ID, ...): Removes a given peer from Chord. Immediately prios to this peers' removal, any data item(s) held by this peer is moved to the peer which will become responsible for key=ID. The finger table of the remaining peers is updated appropriately. This function removes this peer completely. You will need to think about how the removal of an index node affects (the finger table, data items, etc) of the other remaining index nodes. On success this function prints to the screen "PEER < ID> REMOVED". If this function causes the removal of the last remaining peer in the Chord, then all data items are lost (memory freed), and the program is to print Last of the peers removed. CHORD terminated, then your program is to exit.

FindKey(key, ...): This function searches for the peer responsible for the given (hash-) key. This search function must use the finger tables of the peers as described in the lectures and the text book. Follow the algorithm as is described in the book (and illustrated in Figure 5-4) to locate the peer that is responsible for the key. The function prints to standard output the IDs of the peers visited separated by the '>' symbol and a newline character at the end. For example, if a peer with ID = 1 initiated a search and the IDs of the peers visited during the search was 7,12 then this function will print 1>7>12

Hash(string): Computes a hash key for a given data item. You can assume that the data item is a null- terminated string. The algorithm that must be used for this function is shown at the end of this assignment. Ensure that the returned value is within [0;2 n ) by using an operation which connects the end points in the has sequence (, 2ⁿ-2, 2ⁿ-1,0,1,2,...).

Insert(string, ...): This function simulates that an peer inserts a data item into the Chord. The data item is given as a string parameter. The peer will call the function Hash(string) to compute the associated hash-key. The string is then to be stored at the index node that is responsible for the computed key value. Note that the FindKey() function may need to be called in order to locate the node responsible for this data item. Once found, the peer that is responsible for this data item is to store the data item. Note that the data item is stored in a part of the memory that is only accessible by the targeted peer. Note also that this means that a peer may have to store more than one data value (possibly many more than one). This function will print to the screen the string "INSERTED < string> (key=< key_value>) AT" followed by the ID value of the peer at which the data item is stored.

Delete(string, ...): This function simulates that a peer requests the removal of a data item identified by the parameter string from the Chord. You can again assume that the data item is given as a string parameter. Similar as before, this function uses the hash function to compute the associated key value, then FindKey(.) to compute the peer responsible for the data item, then removes the string from the memory of that peer. If successful, this function will print to the screen: "REMOVED < string> (key=< key_value>) FROM" followed by the ID value of the peer from which the string was removed.

Print(key, ...): This function will print information about the peer that is responsible for the given key. Thus, the function may need to call FindKey() in order to find the peer that is responsible for key value. Once found, the target peer will then print "DATA AT NODE < MYID:>", where < MYID> is the ID of the peer, followed by a newline, then followed by the list of all data items (strings) stored at this node (separated by a newline), followed by the string "FINGER TABLE OF NODE < MYID>", a newline, and the content of the finger table of node "MYID".

Read(filename): Reads a set of instructions from a given text file. The file contains one instruction per line. Anything after a hash '#' symbol is to be treated as comment and is to be ignored. The instructions are named analogous to the functions which need to be called. For example, a file may contain the following list of instructions:

initchord 5 #Create a CHORD of size 32
addpeer 7 #Add a new peer whose ID is to be 7
addpeer 3 #Add peer 3...
removepeer 3 #...and remove it again
addpeer 12
addpeer 3
addpeer 9
removepeer 3
addpeer 17
insert THIS IS A TEST
insert Markus Hagenbuchner
insert CSCI319
print 12
delete THIS IS A TEST
print 12
removepeer 0
print 7
print 9
print 12
print 17

Note that each line in the file is terminated by a newline ("\n") rather than a carriagereturn ("\r\n").

When compiled, the program should be executed at a command line and accept the file name of a file containing the instructions. For example, assuming that the compiled code is named CHORD and assuming that the file myfile.dat contains instructions (in the format as was shown before), then the program should be able to run by

./CHORD myfile.dat

this would execute all instructions within the myfile.dat. There is one instruction per line in myfile.dat. Instructions not recognized by your program should be ignored quietly (i.e. no error message). Do not assume a maximum file size for the file that contains the instructions. In other words, the file may contain any arbitrary

A sample output of the chord for the example shown above is given in Attachment 3 below.

Attachments:

Attachment 1: Algorithm of a hash function for character strings:

Given a character string of arbitrary content and length, then the hash algorithm is as follows:

BEGIN Hash (string)
UNSIGNED INTEGER key = 0;
FOR_EACH character IN string
key = ((key << 5) + key) ^ character;
END FOR_EACH
RETURN key;
END Hash

The '<<' is a bit shift operation which shifts bits to the left. Hence, key<<5 shifts the bits in key by 5 positions to the left. Note also that ^ corresponds to the XOR operation, and that character corresponds to the ASC-II value of the character, and that the terminating NULL character is not considered part of a string.

Attachment 2: The Chord system, an example (from the text book): see image.

Attachment 3: Sample output (for the sample script shown above):

This output serves as a guide only. The output (particularly with respect to the search function) can differ.

Markus Hagenbuchner
1234567
0>0
PEER 7 ADDED
0>7
PEER 3 ADDED
0>3
PEER 3 REMOVED
0>7>0
PEER 12 ADDED
0>7
PEER 3 ADDED
0>7>12
PEER 9 ADDED
0>3
PEER 3 REMOVED
0>9>12>0
PEER 17 ADDED
0>9>12
INSERTED THIS IS A TEST (key=11) AT 12
0>9>17>0
INSERTED Markus Hagenbuchner (key=19) AT 0
0>7
INSERTED CSCI319 (key=1) AT 7
0>9>12
DATA AT INDEX NODE 12:
THIS IS A TEST
FINGER TABLE OF NODE 12:
17 17 17 0 0
0>9>12
REMOVED THIS IS A TEST (key=11) FROM 12
0>9>12
DATA AT INDEX NODE 12:
FINGER TABLE OF NODE 12:
17 17 17 0 0
0
PEER 0 REMOVED
7
DATA AT INDEX NODE 7:
Markus Hagenbuchner
CSCI319
FINGER TABLE OF NODE 7:
9 9 12 17 7
7>9
DATA AT INDEX NODE 9:
FINGER TABLE OF NODE 9:
12 12 17 17 7
7>12
DATA AT NODE 12:
FINGER TABLE OF NODE 12:
17 17 17 7 7
7>17
DATA AT INDEX NODE 17:
FINGER TABLE OF NODE 17:
7 7 7 7 7