Read these articles if you haven't already:
What's snapshot for?
- Checkpointing
- Deadlock detection(you can check for deadlocks by periodically talking a snapshot and see if there's a deadlock in the snapshot)
Assumptions(limitation)
1) Existence of channel, and its FIFO
For example, the following CANNOT happen.
It's because B happens before D and D is included in the snapshot. After P1 takes snapshot, it has to send its marker message to P2 before doing anything else. Given that condition, D cannot be included. If it is, it's the violation of FIFO.
2) Reliable delivery
- Messages aren't lost
- No message loss
- No Corruption
- No duplication
3) Processes don't crash while the algorithm is running
Properties
1) It's guaranteed to be terminated
2) Any process can be an initiator process at any time(Decentralized Algorithm).
3) Marker message doesn't have to include an identifier for the snapshot initiator.
4) Causally correct (more on the next section)
Cut
A cut is a "time frontier" going across a Lamport diagram, dividing it into "past" and "future"
An event is "in the cut" if it is on the "past" side of cut.
Meaning of Cut being consistent
A cut is consistent when, for all events F,E that are in the cut, if F->E then F is also in the cut.
So the inconsistent cut would look like:
And then consistent cut would be:
Chandy-Lamport Algorithm determines a consistent cut
If you take the set of events in Chandy-Lamport snapshot, and you make a cut, it's going to be consistent.
