Consistent Cuts and the Marker Algorithm for Global Snapshots

A distributed computation has no single moment at which its state can be photographed. Each process has a local state, each channel has messages in flight, and the only way to collect all of it is to ask the processes one at a time. The collection takes time, and during that time the computation continues. The question the snapshot algorithms answer is which collections of per-process states and in-flight messages correspond to a state the system could actually have been in.

Cuts, and why most of them are impossible

A cut is a set containing one prefix of each process’s event sequence. If process p has executed events e1, e2, e3 and process q has executed f1, f2, a cut might contain {e1, e2} and {f1}. The cut is consistent when it contains no receipt event without also containing the matching send event. Equivalently, the cut is consistent when no event in it has a causal predecessor outside it, which is the statement that the cut is closed under →.

An inconsistent cut is easy to produce and easy to misread. Suppose p sends a message to q and q receives it. If a cut includes q’s receive but excludes p’s send, the cut shows q acting on a message that was never sent. Any state computed from that cut can be a state the system never occupied, which makes it useless as a checkpoint for recovery and misleading as a basis for detecting properties such as deadlock.

The definition is about events, but the state that matters is the union of each process’s state after its last included event, plus the messages that are in flight at the cut — sent before the cut and not yet received at it. That set of in-flight messages is what a snapshot must record, and recording it is the hard part, because a channel has no observable “contents” that can be read at an instant.

The marker rule

The Chandy–Lamport algorithm solves the problem with a control message. An initiator takes its own local snapshot, then sends a marker on every outgoing channel before sending any further application message. A process that receives a marker on an incoming channel, and has not yet recorded its own state, records its state, then forwards markers on all its outgoing channels. A process that receives a marker after it has already recorded its state records the sequence of application messages that arrived on that channel between its snapshot and the marker — that sequence is exactly the set of messages in flight on that channel at the cut.

The markers travel in order with the application messages on each channel, which requires the channels to be FIFO. That requirement is what makes the recorded channel state correct: if a message sent before the marker could arrive after it, the receiver could not tell whether that message was in flight at the cut or sent after it. On a non-FIFO channel the algorithm records a set that may include messages sent after the cut, and the resulting snapshot is not consistent in the required sense.

def on_marker(self, channel):
    if not self.recorded:
        self.state = self.local_state()      # snapshot before forwarding
        self.recorded = True
        for ch in self.outgoing:
            ch.send(MARKER)                  # markers follow the snapshot
        for ch in self.incoming:
            self.channel_state[ch] = []
    else:
        self.channel_state[channel] = self.recorded_since(channel)

Two markers can cross on a channel in each direction, and a process may receive a marker on a channel on which it had already sent one. The algorithm terminates when every process has received a marker on every incoming channel, which in a strongly connected graph happens after each process has forwarded markers around the cycle.

What the algorithm assumes, and what happens when it does not hold

Four assumptions carry the proof, and each fails somewhere in practice.

The first is that no message is lost and no channel fails during the snapshot. A partition during the run leaves some process waiting for a marker that never arrives, and the snapshot never completes. Implementations add timeouts and either abort the snapshot or treat the unreachable component as a separate snapshot, which changes the guarantee from “one global state” to “one state per reachable component”.

The second is FIFO delivery. Many transports do provide per-connection ordering, so this is often satisfied, but a transport that multiplexes several logical streams over one connection, or a datagram transport, does not. A snapshot over such a channel needs a different mechanism, usually a logical clock attached to each message so the receiver can classify it relative to the cut.

The third is that processes do not crash mid-snapshot. A process that fails after sending some markers and before recording its state leaves the other processes unable to complete. Recovery either restarts the snapshot or relies on the surviving processes’ recorded states plus a log.

The fourth is that the computation does not terminate before the snapshot finishes. In a terminating computation the markers may never be forwarded because there are no more events to trigger them, and the algorithm produces a partial collection.

The algorithm also does not stop the computation. Application messages continue to flow during the snapshot, and the recorded channel states account for them. That is the point: the snapshot is taken without a pause, at the cost of recording messages that would otherwise be discarded.

From snapshots to properties

The reason to take a snapshot is usually to evaluate a predicate. A stable property is one that, once true, remains true — deadlock, termination, and loss of a token are the classic examples. A snapshot lets a detector evaluate the predicate on a single consistent state rather than on a stream of inconsistent observations, which is the difference between a detector that can be wrong in one direction only and one that can be wrong in both.

If a stable property holds in the state at some point during the computation, then it holds in any snapshot taken after that point, because the property cannot have become false. Conversely, if the property holds in the snapshot, it held at the moment the snapshot represents, because the snapshot is a state the system actually occupied. The detector therefore reports no false negatives after the fact and no false positives at all, which is exactly the guarantee a monitoring system needs and rarely has.

Message counting and termination detection are the same idea in a smaller form. A process that wants to know when all work is finished can use a snapshot-like wave in which markers carry a count of outstanding messages, and the count reaching zero at the initiator indicates that no work remains. The construction is the basis of several termination-detection algorithms, all of which are variants of the marker rule.

Cost, and the alternative of logical time

The marker algorithm sends O(E) control messages for E channels, and it records channel contents, so the space cost is proportional to the number of messages in flight at the cut. The snapshot itself is O(n) states plus the in-flight messages, and a process must hold its state still long enough to copy it, which for a large state is a real pause.

An alternative formulation uses logical time instead of markers. If every message carries a Lamport timestamp or a vector clock, a cut is consistent exactly when no message received inside the cut carries a timestamp greater than the cut’s frontier. A process can therefore take a snapshot at a designated logical time and classify in-flight messages by their timestamps, without markers. This is cheaper in control messages and more expensive in per-message metadata, and it requires the timestamps to be maintained, which is the cost described in Happens-Before and the Scalar Logical Clock.

The two formulations are the same theorem viewed from different angles: a consistent cut is one closed under causality, and both markers and timestamps are ways of making causality observable at a point in time.