CS505 PA1: Gossip

Programming Assignment 1: Gossip Protocol

Note: Questions are fully expected on this programming assignment. Do not hesitate to post and ask both the professor and TA. Some instruction is below, but it will doubtlessly be insufficient as a comprehensive guide. (complete, but may be updated)

Background/Protocol

The purpose of PA1 is to familiarize yourself with the Mace programming environment while implementing portions of the Demers et al. epidemic/gossip protocol. You should read the Demers paper for familiarity and understanding, but refer to this description for the details of what specifically to implement.

For this project, you may use cloud10.cs.purdue.edu through cloud15.cs.purdue.edu. The access control has not been setup properly yet, but will be setup shortly. The necessary tools for building and running Mace and the model checker should all be available on those machines. You should use cmake to build Mace out-of-source, and within your scratch directory on these machines. (Mace, when compiled, is quite large, and so keeping the build on /scratch will keep your directory from causing you grief from the sysadmins) You are welcome to do this project on any machine on which you can build Mace, which should be generally true of Linux and OSX systems. We will use a departmental gentoo build for testing them. For this project, you only need to submit your final HW1Epidemic.mac. Your first step should be to download Mace using subversion as described here: http://www.macesystems.org/release/. Then, you should open the Mace-HOWTO.pdf document in the docs directory, and work through building Mace and understanding the simple Ping example.

We will be implementing the GossipServiceClass in Mace. That interface is considerably more general than the interface necessary for this class. In particular, it supports channelIds (allowing different independent channels of gossip), and also allows multi-source gossip with the delivery mechanism for gossip supporting indicating the gossip data from each source. You do not need to worry about channel ids or gossip sources. You may assume that all gossiping is on channel 0, and every node should pretend it is the source of the gossip when delivering gossip to the simulated application. In actuality, only one peer will do the publishing. Also note, you need not implement the pull-based downcall to retrieve gossip. Instead, deliver all gossip to the simulated application using the upcall_deliverGossip method.

The protocol you should implement is as follows:

Join Protocol (already implemented in skeleton): Each node is given a bootstrap peer. On maceInit, they should contact their bootstrap node by sending it a Join message. The bootstrap node will respond with a peerset which this peer will use to initialize it's own state. Note: a node should never appear in its own peerset. This protocol is already implemented.
New published data supercedes older published data. This should be handled by using a MonotoneTime to keep track of the version of the data. The model of the gossip service is that there is always a "current" version of the data. Revoking gossip in this implementation is equivalent to publishing an empty string. You also do not need to worry about garbage collection. Since there is always a current gossip value, we will not garbage collect old data.
Rumor Mongering: When new data is published, you should first execute a variant of rumor mongering. Hot rumors should be spread to random peers until the rumor spread is a duplicate to MAX_DUPLICATES peers (set to 3 in the skeleton). To support this requirement, you must wait for a peer to respond before transmitting the gossip to the next random peer. You do not have to track what peers you have already used - if you pick them again they will simply appear as duplicated.
Anti-Entropy: Periodically, a status timer will expire. When that occurs, a peer should check with a random peer to see if it has the same version of the data. If they have different versions, corrective action should be taken. I personally prefer a push-pull model, where versions are compared and data can travel either way, but either alternative (push or pull) are acceptable.

Environment/Development

To get started on the homework, you should setup your environment as follows:

Create a directory, such as "CS505" under mace/services/.

Edit mace/services/CMakeLists.txt, and list CS505 (or your directory name) in the SERVICE_DIRS variable. To avoid problems, place it last. You can also remove all other services EXCEPT interfaces, Transport, and SimApplication, as these will not be needed for this assignment. This will make the build faster and smaller. The diff from this modification should look like:

Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt      (revision 1037)
+++ CMakeLists.txt      (working copy)
@@ -1,4 +1,4 @@
-SET(SERVICE_DIRS interfaces Transport RequestTransport Http File RandTree ReplayTree RanSub Pastry Bamboo Chord GenericOverlayRoute GenericTreeMulticast DHT ScribeMS SplitStreamMS SimApplication)
+SET(SERVICE_DIRS interfaces Transport SimApplication CS505)

 WRITE_FILE(${EXTERNAL_VARS_FILE} "
  # Service Includes and Links" APPEND)

Inside CS505, place HW1Epidemic.mac and SimHW1App.mac. HW1Epidemic.mac is the file you will be editing. I took my solution, and removed sections of the code, replacing them with an elipsis (...) in a comment. SimHW1App.mac is the test driver you will use to test your implementation in the model checker. You are invited to read it and become familiar with it, but you are not required to develop anything in it. You are also welcome to edit it to test different things than those tested, though you will not be submitting your modifications.
Place CS505Tests.cc in mace/application/modelchecker/.

Edit mace/application/modelchecker/CMakeLists.txt, and add CS505Tests.cc to modelchecker_SRCS next to ServiceTests.cc (the first time modelchecker_SRCS appears in the file). The diff from this modification would appear like:

Index: CMakeLists.txt
===================================================================
--- CMakeLists.txt      (revision 1037)
+++ CMakeLists.txt      (working copy)
@@ -1,6 +1,6 @@
 IF(${PROJECT_NAME} STREQUAL "Mace")
 SET(APPS modelchecker)
-SET(modelchecker_SRCS ServiceTests.cc ${EXTERNAL_TEST_SRCS})
+SET(modelchecker_SRCS ServiceTests.cc CS505Tests.cc ${EXTERNAL_TEST_SRCS})
 SET(LIBNAME MaceMC)
 ELSE(${PROJECT_NAME} STREQUAL "Mace")
 SET(APPS ${PROJECT_NAME}_modelchecker)

Edit mace/application/CMakeLists.txt to remove all applications other than the model checker. To do so, comment out all lines except for ADD_SUBDIRECTORY(modelchecker), by prefixing each line with a sharp (#).

You should now be able to build the repository with your new services. Create a build directory, then run:

cmake /path/to/mace/source

to create the build system. Henceforth, you should be able to build your system using 'make'.

When editing Mace files (.mac), it is helpful in most editors to use the syntax highlighting for C++. If you are a Vim user, there is a vim syntax file you can use.

Model checking / Debugging

To run and debug this project, we will be using the Mace modelchecker. To familiarize yourself with MaceMC, you should next follow the HOWTO in mace/docs/modechecker/tex/MCHowTo.pdf. This will take you through a BrokenTree example, and finding some simple bugs using the model checker. To setup your environment for model checking:

First, compile Mace
Then, create a symbolic link from the compiled modelchecker into mace/application/modelchecker directory in the source code. (The Mace scripts all assume the model checker resides there based on prior setup). You should find the modelchecker binary in the build/mace/application/modelchecker/ directory.
Create a subdirectory under the model checker, for example "HW1". Place params.default into that directory.
In params default, you can change the number of nodes to expermient with, as well as whether to allow UDP errors and reordering. Other parameters should probably remain the same.
To run the model checker, change to the HW1 directory, then execute "../run-modelchecker.pl". It will start searching. If it finds an error, it will output a number of files. The run-modelchecker.pl script will automatically generate a complete logfile of the erroneous run, as well as a graph of the execution. It will name these error files error.log and error.graph. Error.graph contains control characters which color the output on most terminals. Rather than looking at error.log directly, we recommend using mdb (../mdb error.log), which will open an interactive logfile debugger, allowing you to look at the execution, one step at a time. Each step will end with an output of the system state (state of all nodes in the system).

If the model checker is not finding bugs, it will output lines of code such as:

3.0.0.0:10201 [Sim::pathComplete] Path 94208 ( 88306 in phase) ended at simulator step: 107 random step: 144 cause: STOPPING_CONDITION (OK) Path<sdepth=10>SimRandUtil<prefixlen=0,position=144,searchlen=10,walklen=134> search sequence [ 0 0 0 2 0 3 3 2 0 3 ]
10.0.0.0:10201 [Sim::pathComplete] Path 94464 ( 88562 in phase) ended at simulator step: 189 random step: 254 cause: STOPPING_CONDITION (OK) Path<sdepth=10>SimRandUtil<prefixlen=0,position=254,searchlen=10,walklen=244> search sequence [ 0 0 0 2 0 3 3 11 1 3 ]

Each line represents an execution which completed. It contains the path number, which indicates how many paths have been completed so far. It also tells you a number of other statistics such as how long the path was in simulator steps and random number requests, the length of the search sequence, and the search sequence itself. These give you an understanding of the progress in the search.

Standalone Gossip application (for hand-testing)

For the purpose of easy hand-testing and debugging in the initial stages, you can use the following simple application.

Create a new directory in (source directory) mace/application, such as "CS505" and download gossip.cc and CMakeLists.txt into it.
Edit mace/application/CMakeLists.txt and append the line "ADD_SUBDIRECTORY(CS505)".
Build the project from mace/build using make. You should now get an executable file mace/build/application/CS505/gossip.
Run the executable without any arguments to get help. Essentially you should be able to run multiple instances as
```
./gossip -MACE_PORT 9010 -bootstrap cloud15:9010
./gossip -MACE_PORT 9020 -bootstrap cloud15:9010
```
and so on (assuming these are executed on cloud15). The process instantiated with itself as bootstrap will print options to publish data; others will listen for gossips. Feel free to change the application for different settings.

Useful hints:

mdb assumes that the mace source directory is present in your home folder. It is recommended to create a symbolic to mace/ from the home folder.
The ServiceClass and Handlers for Gossip can be found at mace/services/interfaces/Gossip[ServiceClass,DataHandler].mh. upcall_deliverGossip requires a GossipMap containing the MaceKey of the local node and the gossip data.
NodeSet is an extension of std::set and represents a set of MaceKey's.
For generating random numbers, use RandUtil::randInt. Incidentally, NodeSet has a 'random' which does not take any arguments and returns a random element.

Submission and Grading:

Submit only the file HW1Epidemic.mac, using BlackBoard. You can find the submission section in the "Assignments" section of BlackBoard for the class. Submissions will be graded according to this grading rubric (TXT).