Project 2: Chandy-Lamport Distributed Snapshots

Exploring global state consistency in distributed systems

Introduction#

Recording a consistent global snapshot of a distributed system’s state. This is an individual project. The complete project, design document and implementation, is due by 11;59PM on Friday, 11/06.

Starter Code#

https://github.khoury.northeastern.edu/cs4730/chandy-lamport-starter-code

Submitting Your Project#

All the files in the starter code, your source code modifications, and design.pdf should all be placed in the root directory of a compressed archive (i.e., a .zip file) and then uploaded to Gradescope. Alternatively, you can check all these items into Khoury’s GitHub, download a zip file from Khoury’s GitHub, and submit that to Gradescope, or any other upload/submission option Gradescope permits.  If your submission is missing any required file for evaluation, it will receive 0 points.

Currently there is NO autograder for this project.  Until one exists, your submission will be evaluated by hand, using the test framework supplied with the project.

There is no design discussion for this project. Include your design document, design.ps in your submission.

Overview#

You will implement the Chandy-Lamport snapshot algorithm on top of a simulated distributed system. Nodes hold tokens and pass them to each other over directed channels. A snapshot must capture a consistent global state: every node’s token count plus every token message that was in flight on every channel at the “moment” of the snapshot. Since no tokens are created or destroyed, a correct snapshot always adds up to the system’s total.

The simulator is single-process and deterministic: the same seed always produces the same run. You can debug with print.

System model#

Channels are directed, reliable, and FIFO, with arbitrary but finite delay (1 to max_delay ticks). The graph is strongly connected. Any node may start a snapshot at any time, and multiple snapshots may be in progress at once, so your node must keep separate state for each snapshot_id.

What you implement#

Only chandy_lamport/node.py. Fill in start_snapshot (called when this node initiates a snapshot) and handle_message (called for every arriving token or marker). You will probably want a few helper methods of your own.

The API available to your node is documented at the top of node.py and in framework/base_node.py. Two calls deserve special attention.

• record_local_state(snapshot_id) must be called exactly once per snapshot, at the exact moment the algorithm records this node’s state; use its return value as your token count.
• report_snapshot(LocalSnapshot(...)) must be called exactly once per snapshot, after a marker has arrived on every inbound channel.

The channel_messages dictionary in your LocalSnapshot must have one key per inbound neighbor, mapping to the list of TokenMessages recorded on that channel, in arrival order.

Do not modify anything in framework/ or self._sim. We will use the original versions when evaluating your submission.

Running#

Requires Python 3.10+ and no extra packages.

python -m unittest tests.test_basic -v       # small hand-traceable cases: start here
python -m unittest discover -s tests -t .    # everything
python run_example.py --verbose              # watch an event trace

To debug a single scenario, construct a Simulator with verbose=True and use self.log(...) in your node.

How you are evaluated#

framework/checker.py compares your snapshot to the ground truth. For every channel i→j it computes exactly which messages should have been recorded (those sent by i before i recorded its state and received by j after j recorded its state) and checks your answer message by message. Token conservation alone is not enough to be correct.

Hints#

Think carefully about these questions before you write code.

• What should a node do when it sees a marker for a snapshot for the first time?
• What is the recorded state of the channel that the first marker arrived on?
• Which channels should you record, and when do you stop recording each one?
• If two snapshots are in progress, can one incoming token message belong to the recorded state of both?