Chandy-Lamport Snapshots

What exactly is the Chandy-Lamport Snapshot algorithm doing? Why? What’s the implication of a “violation”?

Here is an example I cooked up that may help.

Consider you are a bank with three branches at P, Q and R locations. Say you are the only bank in the world, and people transact by sending money across your different branches. So the total amount of money across all your branches should always be the same. Say each branch starts with $100 — that is $300 in all.

Now, suppose the country’s Government/Regulator wants the Bank to take “snapshots” at regular intervals for auditing purposes. What is one property that all the snapshots should have?

It should account for ALL of the $300 in the economy. Nothing less, nothing more.

With this setup in mind, here is a drawing of an example timeline (handwritten, sorry):

If the PDF does not load, click here to open it directly.

Each message is a transaction saying some money was sent, and displaying the total amount of money at each end. E.g. Message A → B is sending $10 from P to Q. So P will have $90 when the message is sent and Q will have $110 when the message reaches. Q starts the snapshot at point I.

The example demonstrates the following:

  1. Why are just local snapshots not enough (at points I, J, K in the timeline)? Why does CL have to do all the marker-message and channel stuff?
  2. What happens when we introduce some “violations”? On page 2, I show two different kinds of violations. One where the snapshot captures only $280 in the banks, and one where you think it’s $320.

Now, every problem in real life is different and you can’t individually try to find the equivalent of “total should always be $300” for your specific problem. That is why the CL algorithm formalizes the concept of a “Consistent Cut”. i.e. If the cut you capture is consistent, then that snapshot carries ALL the information you need about the system to do any kind of replaying/debugging/auditing etc. And as the example demonstrates, that “cut” is not just a collection of local states, but also of the channels.

Hope this helps with intuition for Chandy-Lamport Snapshots.