Discussion for: K. Mani Chandy and Leslie Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems" (TOCS, 1985)

Paper overview

This fundamental paper written by Chandy and Lamport presents the Chandy-Lamport Snapshot Algorithm, an algorithm for determining and saving the global state of a distributed system at any point in time. This algorithm serves as the basis for processes like deadlock detection, termination detection, and checkpointing. The most fascinating part of this algorithm is that it does not require a synchronized global clock or shared memory. It works by initiating a snapshot from any one process, and sends a marker message to every other process in the system. Processes then initiate snapshots on their own process if it's the first marker message they've seen, or end a snapshot if they have already seen a marker. Each process continues to send markers along its outgoing channels after recording its state. The algorithm terminates once every process has recorded its state and the state of all incoming channels. The other significant contribution is the definition of stable properties, which are system states that persist once true (e.g. deadlock or completion). The snapshot algorithm is presented as a method for stability detection and the resulting snapshots can verify such properties.

Discussion questions

Q1 (easy warm-up question)

In a complete, terminating run of the Chandy-Lamport algorithm in a system of three processes, how many marker messages will be sent? In general, in a system of N processes, how many marker messages will be sent in a complete run?

Discussion summary for Q1

In a complete, terminating run of the C-L algorithm, there will be N * (N - 1) total marker messages sent, which can be written as N^2 as the number of processes approaches infinity. This is true because in the algorithm, every process will send a marker message to every other process in the distributed system. We can also derive this number from the total number of channels in the system as every process must be able to communicate with the other processes. For example, if there are 3 total processes in the system, we will have 3 * (3 - 1), or 6 total marker messages sent, which is also the number of channels in the system.

There was also some discussion on a graph that was not complete, and while in practical applications this would not be a case to consider, theoretically, we can say the number of marker messages is simply the number of edges in that graph. Edges are considered channels, and vertices are considered processes or nodes in the system.

Q2

(question contributed by Rachel Park)

In class, a snapshot was considered consistent if given any event e that is in the snapshot, for all events e' such that e' happens before e, e' is also in the snapshot. How does the paper's definition of a consistent global state (pg 70) differ from or relate to this definition? Specifically, the paper includes the number of messages sent and received between channels as part of its definition. How might including this information impact the understanding of a consistent global state?

(Note from Lindsey: in class, our notion of a "consistent snapshot" was really only about the recorded process states, and did not take the recorded channel states into account. Chandy and Lamport's notion of a consistent snapshot, however, also takes the recorded channel states into account.

The snapshots taken by the C-L algorithm are certainly consistent according to the definition we gave in class. But since C-L snapshots also contain recorded channel states, we ought to be able to say something about how those recorded channel states fit in with the rest of the snapshot. That is what this question is getting at.)

Discussion summary for Q2

The paper includes an extra channel state which is different from only have sender and receiver state. In the paper, the author considered that a channel should receive and send the same amount of messages to keep the “definite = true” condition. The message number that is received along the channel should not exceed the message number that is sent out. The “n>=m” situation happens because the “sending” recording is accurate but the “receiving” recording may be affected by accident so the “receiving” recording has less number than the “sending” recording. Basically, the number of sent messages should be the same as the number of received messages for each process over the channel in the snapshot. The benefit of having a channel state for snapshots is to keep extra causality for each process. The extra information simplifies the logic that needs to be considered when recovering a system by using this snapshot.

Q3

The Chandy-Lamport algorithm assumes that channels are FIFO: messages are received in the order they are sent. Both the marker messages of the snapshot algorithm and the application messages of the application being snapshot must travel along these FIFO channels. Given an example of how a snapshot might "go wrong" if channels were not FIFO, say, if an application message violated the FIFO rule and "crossed over" a marker message in a channel. (It would be useful to draw a picture.)

Discussion summary for Q3

If channels are non-FIFO in the Chandy-Lamport snapshot algorithm, application messages could "cross over" the snapshot marker messages, leading to an inaccurate snapshot. Suppose p1 sends an application message to p2 at event A followed by a marker message to initiate the snapshot. If the channel between p1 and p2 is non-FIFO, the marker could reach p2 first at B, before the application message. This would result in p2 taking a snapshot of its state without recording the application message, effectively "losing" it from the snapshot. This reordering misrepresents the global state, as it omits or duplicates messages depending on their arrival order relative to the marker. In real-world applications, such as banking, this could mean missing a money transfer in the snapshot, leading to an incorrect account balance. In voting systems, a vote might be counted extra or missed entirely. The FIFO assumption is crucial to ensure each process's snapshot accurately reflects the true system state at the time of the snapshot initiation.

Bonus question Q4 (optional; only do this if you have time)

In section 3.3 of the paper, Chandy and Lamport say, "The algorithm can be initiated by one or more processes, each of which records its state spontaneously, without receiving markers from other processes." (Emphasis mine.) Consider the example run of the algorithm that we walked through in class last time. In our example, P1 initiated the algorithm. Walk through the example and convince yourself that we would still have a consistent snapshot if P2 also independently decided to initiate the algorithm at around the same time. Why is it important and useful that more than one process can initiate the algorithm at once?

Discussion summary for Q4 (if we get to it)

[to be filled in by scribes, if we get to it]