Distributed Snapshot

A consistent cut is the fundamental property of a valid distributed snapshot. It captures a global state where if a receive event for a message is included in the snapshot, then the corresponding send event for that message must also be included. This prevents the snapshot from containing a message that was never sent, ensuring logical causality is preserved. The Chandy-Lamport algorithm is the canonical method for recording such a consistent cut in a message-passing system.

A key goal is to capture the snapshot without stopping or significantly impeding the normal execution of the underlying distributed application. Algorithms achieve this by piggybacking control messages (like markers) on regular communication channels. This allows the system to continue processing transactions and exchanging data while the snapshot protocol executes concurrently, making it suitable for live production systems.

The snapshot is not a single value but a composite state vector. It comprises:

• The local state (e.g., variable values, stack) of each process at the moment it records its snapshot.
• The state of all communication channels, captured as the set of in-transit messages that were sent before the sender's snapshot but received after the receiver's snapshot. This complete vector represents the system's state as if all processes were frozen simultaneously.

A primary use is detecting stable properties—conditions that, once true, remain true forever (e.g., deadlock, termination, or a completed computation). If a stable property holds in a consistent global snapshot, it holds in the actual global past of the system and will continue to hold. This allows for efficient detection without continuous monitoring of the entire execution history.

The snapshot protocol must respect happened-before relations. The recorded state for each process is causally dependent on the states of other processes up to the cut. This property is what enables the snapshot to be used for debugging and recovery, as it represents a state that could have occurred during a legal execution of the system, free from temporal paradoxes.

Capturing the state of asynchronous communication channels is complex. The algorithm must record all messages that are in flight across the cut. This is typically done by having each process record messages received on a channel after it records its local state but before it receives a marker message on that channel. The set of these recorded messages defines the channel's state in the snapshot.

A distributed algorithm that enables a group of processes or agents to agree on a single data value or sequence of actions despite the possibility of failures. Consensus is often a prerequisite for taking a coordinated, consistent snapshot in systems without a single coordinator.

• Paxos and Raft are classic examples used to agree on log entries or system state.
• In multi-agent systems, consensus may be used to agree on when to initiate a snapshot protocol or what the final agreed-upon state is.

A logical clock mechanism used to capture causal relationships between events in a distributed system by assigning each process a vector of counters. They are crucial for understanding the partial ordering of events that lead to a specific system state.

• Unlike Lamport timestamps, vector clocks can detect concurrent events.
• When analyzing a distributed snapshot, vector clocks help reconstruct the causal history of messages and state changes, verifying the snapshot's internal consistency.

The seminal algorithm for capturing a consistent global snapshot of a distributed system. It works by having an initiator process send a special marker message along all its outgoing channels.

• The algorithm assumes FIFO (First-In, First-Out) channels.
• Upon receiving a marker for the first time, a process records its local state and propagates the marker. It also records the messages received on each channel after recording its state and before receiving that channel's marker, which defines the channel state in the snapshot.

A consistency model for distributed data stores that guarantees if no new updates are made to a given data item, all accesses will eventually return the last updated value. This model often forgoes the strong guarantees needed for an instantaneous global snapshot.

• Systems built on eventual consistency (e.g., using CRDTs) may use distributed snapshots for auditing or debugging the eventual state, rather than for real-time coordination.
• Snapshots in such systems represent a possible past state that the system passed through on its way to convergence.

A consistency model where any read operation on a data item returns a value corresponding to the result of the most recent write operation, as perceived by all nodes. A distributed snapshot, when taken, aims to capture a state that is strongly consistent across all participants.

• Achieving a strongly consistent snapshot often requires coordination (e.g., a global barrier or lock) that pauses system progress.
• This contrasts with weaker models where a snapshot might only reflect a causally consistent or monotonically consistent view.

A primary application of distributed snapshots. A checkpoint is a persistent snapshot of a system's state saved to stable storage, enabling rollback recovery in case of failures.

• Coordinated Checkpointing: Uses a protocol like Chandy-Lamport to create a globally consistent checkpoint, simplifying recovery but pausing application.
• Uncoordinated Checkpointing: Processes save states independently, leading to a domino effect during rollback unless combined with message logging.
• Essential for fault tolerance in long-running multi-agent workflows.