IMPORTANT: This assignment may be done in pairs and you are strongly encouraged to do that. Late assignments penalized at 33.333% per day pro-rated. Late assignments not accepted after 2 days
In this assignment you will implement the vector time-stamp algorithm and then use the logs produced by your program to trace runs of the bully election algorithm. To visualize the bully algorithm you will use the software package ShiViz developed by Ivan Beschastnikh and his students here at UBC.
To use ShiViz you need to produce a log file with events tagged with a vector time-stamp. Although the tool is quite configurable, for this assignment an event consists of two or more lines. If there are N lines to an event, then the first N-1 lines are some sort of description of the event, and the last line is the vector time-stamp for that event. For this assignment you will probably want to use two lines, one for the event description and then the vector time-stamp line.
The vector time-stamp rules used by ShiViz are a bit different from those discussed in class. In class we only incremented a node's clock just before it sent a message. It was noted that we could actually increase the clock at anytime we wanted since we could imagine a node whose role was unimportant to our algorithm as the recipient of a message every time we wanted to update the clock. Given that, the rules to use for the clock update and logging are as follows:
Each "node" is to keep its own event log file. Here are some examples of the log file format you need to produce for ShiViz:
Starting N1
N1 {"N1":1}
Send Election MSG to N2
N1 {"N1" : 2}
Send Election MSG to N3
N1 {"N1" : 3}
Receive Answer
N1 {"N1" :4 , "N2" : 3}
Receive Answer
N1 {"N1": 5, "N2" : 3, "N3" : 3}
Receive COORD
N1 {"N1": 6, "N2" : 4, "N3" : 6}
In the above example, each two lines are an event. The first line of the two is some sort of description of the event and is free format. The 2nd line is the vector time of the event. Each vector time line starts with the identifier of the node. The time then consists of JSON tuples identifying the time at all known nodes. A known node is one that a clock value has been received for either directly or transitively. You don't include nodes that are supposed to exist but you don't know the time of. Also observe that the initial clock value at a node is 1. The time vector is enclosed between "{" and "}". Each time value consists of the node identifier in quotes, followed by a ":" and then the time. Individual times are separated using a ",".
For ShiViz to work it needs to know the events from all the nodes. Here are the two log files for nodes N2 and N3 that need to be combined with the above log file to allow ShiViz to diagram things out.
N2's Log file
Starting N2
N2 {"N2" : 1}
Receive Election MSG
N2 { "N1" : 2, "N2" : 2}
Send Answer
N2 {"N1" :2, "N2" :3}
Send Election GG
N2 {"N1" : 2, "N2" :4}
Receive Answer GG
N2 {"N1" : 2, "N2" : 5, "N3" : 5}
Receive COORD
N2 {"N1" :3, "N2": 6, "N3" : 6}
N3's log file
Starting N3
N3 {"N3" : 1}
Receive Election MSG
N3 { "N1" : 3, "N3" : 2}
Send Answer
N3 {"N1" :3 , "N3" :3}
Receive Election MSG GG
N3 {"N1" :3 , "N2" : 4, "N3" :4}
Send Answer GG
N3 {"N1" :3 , "N2" : 4, "N3" :5}
Send Coord
N3 {"N1" :3, "N2" : 4, "N3" : 6}
To try ShiViz follow this link: http://bestchai.bitbucket.org/shiviz/
and then click the "Try out ShiViz" button. Cut and past the above
log files, one after the other, into the text box on the right. You
then need to enter into the "Log parsing regular expression:" the
regular expression shown below.
(?<event>.*)\n(?<host>\S*) (?<clock>{.*})
Click on visualize to see a graph of the events and message exchanges. Instead of cutting and pasting you could also cat the log files together and then upload the file. You are strongly encouraged to explore ShiViz and the log file format to get a better understanding of the type of information you want to use to name/describe the event and how the vector clock values need to change, and what to log to provide so that the resulting diagram provides the most useful information. A slightly more elaborate log file has been provided in the repo for this assignment.
You are program in C, the bully algorithm using UDP and with each message sent as part of the algorithm you are to include the vector time stamp (see the files in the repo).
Your program is to be named node and take 4 parameters. The program must compile and run on the Linux undergraduate machines provided by the department. Having a solution that works/compiles on a different machine but not the department's Linux machines will be awarded 0 for all code related marks, so make sure it works. The 4 parameters the program is to take, in the listed order are:
The above parameters are not optional and must always be provided. If a number parameter cannot be converted to a number an error is to be reported and the program is to exit. With respect to file names, if a file needs to be opened and cannot, then an error is to be reported and the program is to exit.
If you want you may add additional parameters after these to aid in program development and debugging. However these parameters must be optional such that if the program is run without the optional parameters it behaves as required.
hostname portNoWhere nodeNumber is an integer value that is the node's number, the hostname is the hostname or IP address where that node resides, and the port number is the port the node is listening for UDP packets on. An example file might be something like this:
localhost 1856 localhost 1857 remote.ugrad.cs.ubc.ca 2000
On starting the node will read the above file and build the list of group members. A node's ID will be its port number. (When printing a node number in a log put an N in front. For example N1856) Since the port number is the Node ID, this implies that the port numbers have to be unique regardless of what node the program is running on. You may assume that all lines are properly formatted and that the various fields are separated by a single space and that there are no leading blanks on a line. Your program, however, is to exit gracefully with an error message if the file cannot be opened for reading. Your program must be able to handle 8 nodes plus itself. For vector time-stamp purposes you are to assume that the vector clocks sent in messages all have 9 entries, although some of them may be unused.
In the repo, the file msg.h contains the definition of the message to be sent along with the definitions of the message types.
Although UDP is an unreliable protocol in most situations on a local area network, of the same machine, packets get through. To simplify things you are to assume that all UDP packets sent are received, even though that may not be the case. (If you implement the algorithm properly this won't matter, and in the worst case an election will be called when one wasn't needed.)
To simulate network problems you are to use the SendFailure parameter to determine if the packet should actually be sent or just dropped. If the value is 0 then no packets are dropped. To determine if a packet is to be dropped generate a random number from 0 to 99 inclusive and if the number is less than the SendFailure value then the packet is dropped, otherwise it is sent.
All work is to be handed in via stash. Do not, any any circumstances hand-in object code, executable files, or any other form of binary file and that includes word or PF documents. Make sure you hand-in: