Chandy-Lamport algorithm

The Chandy-Lamport algorithm is a snapshot algorithm for distributed systems, used to record a consistent global state of an asynchronous system. It was developed by and is named after Leslie Lamport and K. Mani Chandy. According to Lamport's own website, the problem came up during a visit to Chandy at the University of Texas at Austin, where Chandy posed it over dinner; by the next morning Lamport had a solution and found Chandy waiting with the same one. The algorithm assumes that there are no failures, that every message arrives intact exactly once, that communication channels are unidirectional and first-in first-out, that a path exists between any two processes, and that taking a snapshot does not interfere with the normal execution of the processes. It works through marker messages. A process that starts a snapshot records its local state and sends a marker on each outgoing channel. A process receiving its first marker records its own state, records the channel the marker came from as empty and sends markers on all its outgoing channels. A process that receives a marker after it has already recorded its state records that channel as carrying the messages received since it first recorded its state. Lamport considers the algorithm a straightforward application of the ideas in his article on time, clocks and the ordering of events in a distributed system.