# Assignment 2: Chandy-Lamport Distributed Snapshots

Introduction

In this assignment you will implement the Chandy-Lamport algorithm for distributed snapshots. Your snapshot algorithm will be implemented on top of a token passing system, similar to the ones presented in slides and in the Chandy-Lamport paper. The algorithm makes the following assumptions:

There are no failures and all messages arrive intact and only once
The communication channels are unidirectional and FIFO ordered
There is a communication path between any two processes in the system
Any process may initiate the snapshot algorithm
The snapshot algorithm does not interfere with the normal execution of the processes
Each process in the system records its local state and the state of its incoming channels

Software

You will find the code under this directory. The code is organized as follows:

server.go: A process in the distributed algorithm
simulator.go: A discrete time simulator
logger.go: A logger that records events executed by system (useful for debugging)
common.go: Debug flag and common message types used in the server, logger, and simulator
snapshot_test.go: Tests you need to pass
syncmap.go: Implementation of thread-safe map
queue.go: Simple queue interface implemented using lists in Go
test_common.go: Helper functions for testing
test_data/: Test case inputs and expected results

Of these files, you only need to turn in server.go and simulator.go, i.e., your commit could only contain changes to these two files. However, some other files also contain information that will be useful for your implementation or debugging, such as the debug flag in common.go and the thread-safe map in syncmap.go. However, you do not have to use the provided SyncMap if you would prefer to implement its functionality yourself. Your task is to implement the functions that say TODO: IMPLEMENT ME, adding fields to the surrounding classes if necessary.

Testing

Our grading uses the tests in snapshot_test.go provided to you. Test cases can be found in test_data/. To test the correctness of your code, simply run the following command:

  $ cd 586/assignment2/
  $ export GOPATH="$PWD"
  $ cd src/
  $ go mod init a2
  $ cd chandy-lamport/
  $ go test
  Running test '2nodes.top', '2nodes-simple.events'
  Running test '2nodes.top', '2nodes-message.events'
  Running test '3nodes.top', '3nodes-simple.events'
  Running test '3nodes.top', '3nodes-bidirectional-messages.events'
  Running test '8nodes.top', '8nodes-sequential-snapshots.events'
  Running test '8nodes.top', '8nodes-concurrent-snapshots.events'
  Running test '10nodes.top', '10nodes.events'
  PASS
  ok      _/path/to/chandy-lamport 0.012s

To run individual tests, you can look up the test names in snapshot_test.go and run:

  $ go test -run 2Node
  Running test '2nodes.top', '2nodes-simple.events'
  Running test '2nodes.top', '2nodes-message.events'
  PASS
  ok      chandy-lamport  0.006s

## Point Distribution

Test	Points
2NodesSimple	13
2NodesSingleMessage	13
3NodesMultipleMessages	14
3NodesMultipleBidirectionalMessages	14
8NodesSequentialSnapshots	15
8NodesConcurrentSnapshots	15
10Nodes	16

## Submitting Assignment You hand in your assignment as before. ```bash $ git commit -am "[you fill me in]" $ git tag -a -m "i finished assignment 2" a2-handin $ git push origin master a2-handin ``` Submit your assignment on Autolab (https://autograder.cse.buffalo.edu/).

Recall, in order to overwrite a tag use the force flag as follows.

```bash $ git tag -fam "i finished assignment 2" a2-handin $ git push -f --tags ``` You should verify that you are able to see your final commit and tags on the Github page of your repository for this assignment.