Chandy-Lamport Algorithm(1) - Consistent global snapshots

Consistent global snapshots

These are ways that potential causality is used in distributed system:

• Determining order of events after the fact(debugging)
• Causal ordering of events as they're happening
• Consistent global snapshots

If A -> B and B is in the snapshot, than A should be in that snapshot, too.

What does it mean by having global snapshot in the distributed system?

So far, individual processes have their own state and the state of the process amounts to all of the events that have taken place on it.

If we had globally synchronized time of day clock, we could say:

"okay you processes take a snapshot of yourself at 10:14PM."

But we CANNOT do that because my 10:14PM isn't the same as your 10:14PM.

What we need is therefore some algorithm that will allow us to take a global snapshot that actually makes sense.

Of many, the classic algorithm for doing that is Chandy-Lamport algorithm - Yes, Lamport again.

Chandy-Lamport algorithm

The new piece of terminology to understand how this algorithm works is Channel which is defined as:

A connection from one process to another

From the following picture, we have two channels:

The channel from p1 to p2 is called, c12 and from p2 to p2 is called c21. To generalize, Cij is the channel from process i to process j.

Now, looking back to the picture, with the notion of channel, we could say C12 is empty because A is already sent to p2 and it became B. The message C is, however, being sent from p2 to p1 and still in the channel C21.

The assumption here is that channel will act like FIFO queues.

How is this related to global snapshot?

Let's say p1 decides to take a snapshot. A takes the snapshot right after message A is sent. Right after(before doing anything else!) it records its state(s1), it sends marker message(in blue arrow) to all of its outgoing channels, namely c12 in this case.

After sending the marker message, it starts recording the messages it receives on all of its incoming channels(c21).

When p2 receives marker message what happens is

• If it's the first marker that process has seen, it records its state and marks the channel(c12) empty and sends a marker to all of its outgoing channel.

• If it has already seen the marker message before, it stops recording on that channel(c12) and set that channel's final state as all of the incoming messages that arrived since recording began.

Look at the diagram above, p1 received marker message from p2 and it stops recording on its incoming channel that the marker message came in on(c21).

During the snapshotting, p1 already received D and that message goes into recorded state too(denoted as expanded). So now we have everything recorded.