Global state (computer science)

Template:Prod llm/dated A global state of a distributed system is the tuple of all process local states and the contents of all communication channels at a particular instant. Because distributed systems lack shared memory and a global clock, no single process can observe all local states and in-transit messages simultaneously.

A naive assembly of local states collected sequentially, without coordination, produces a global state that may not correspond to any state the system actually passed through. A message sent before one process's state is recorded but received after another's can appear to have vanished or been duplicated, yielding a logically impossible snapshot.

A global state is consistent if it corresponds to a state through which a possible execution of the system could have passed: formally, no message is recorded as received unless it is also recorded as sent. This notion, introduced by K. Mani Chandy and Leslie Lamport in 1985, is also expressed as a consistent cut of the system's execution history. Chandy and Lamport proved that any consistent global state is reachable from the system's initial state, and the actual current state is reachable from any recorded consistent global state.

Consistent global states underpin deadlock detection, termination detection, distributed garbage collection, checkpointing for fault tolerance, and distributed debugging. They are sufficient for evaluating stable predicates, properties that once true remain true, without requiring the system to pause.

System model

The model adopted by Chandy and Lamport consists of a fixed set of $n$ processes $p 1, p 2, \dots, p n$ connected by directed FIFO channels.^[1]^[2] Channel $c ij$ carries messages from $p i$ to $p j$ . Channels are reliable: they deliver messages in order without loss or duplication, and a directed path exists between every pair of processes.

Each process executes a sequence of three types of events: a send event on an outgoing channel, a receive event on an incoming channel, or an internal event that changes local state without communicating.^[1]^[3] The local state $s i$ of process $p i$ after an event is the information sufficient to determine $p i$ 's future behaviour. The channel state $M ij$ is the sequence of messages sent on $c ij$ that have not yet been received; these are the messages in transit on that channel at a given instant.

The happened-before relation on events, introduced by Lamport in 1978, provides a partial order: event $e$ happened before event $f$ if $e$ and $f$ are events of the same process and $e$ precedes $f$ , or if $e$ is a send and $f$ is the corresponding receive, or if there exists an event $g$ such that $e$ happened before $g$ and $g$ happened before $f$ .^[2]

Global state

A global state of the system is a tuple

G S = (s_{1}, s_{2}, \dots, s_{n}, M_{12}, M_{13}, \dots, M_{n (n - 1)})

consisting of a local state $s i$ for each process $p i$ and a channel state $M ij$ for each channel $c ij$ .^[1]^[4] The channel state $M ij$ records the sequence of messages in transit on $c ij$ : those sent by $p i$ but not yet received by $p j$ .

As a mathematical object, a global state need not correspond to any instant that was simultaneously observable from a single vantage point.^[2] Two processes may have their local states recorded at different real times, and messages in transit during that interval may appear in neither process's local state.

Example. Consider three processes $p 1$ , $p 2$ , $p 3$ . If $p 1$ has sent message $m 12$ but $p 2$ has not yet received it, a global state recording $p 1$ 's post-send state and $p 2$ 's pre-receive state must record $M 12$ containing $m 12$ to account for the message in transit. Omitting $m 12$ from the channel state would produce a global state no real execution could pass through.

Consistent global state

The consistency condition

An execution history of the system is the set of all events partially ordered by the happened-before relation. A cut $C$ is a partition of the execution history into a past set and a future set such that if event $f$ is in the past and $e$ happened before $f$ , then $e$ is also in the past.^[3]^[2] The frontier of the cut for process $p i$ is the last event of $p i$ in the past of $C$ ; the corresponding local state $s i$ is $p i$ 's contribution to the global state defined by $C$ .

A cut is consistent if for every receive event in the past of $C$ , the corresponding send event is also in the past of $C$ .^[1] Equivalently, the channel state $M ij$ contains exactly the messages sent on $c ij$ by events in the past of $p i$ that have not yet been received by events in the past of $p j$ . A global state defined by a consistent cut is a consistent global state, also called a consistent snapshot.^[1]^[3]

Why naive collection fails

Diagram showing three process timelines with marker messages propagating along channels

Three-process illustration of consistent-cut marker propagation.

If an observer records local states sequentially (first querying $p 1$ , then $p 2$ , without coordination), the result need not be a consistent global state.^[2] Suppose $p 1$ sends message $m$ to $p 2$ between the two observations: the observer records $p 1$ 's state after the send (so $m$ does not appear in $p 1$ 's local state) and $p 2$ 's state before the receive (so $m$ does not appear in $p 2$ 's local state or in the recorded channel state). Message $m$ has vanished: the recorded global state has no trace of it, which no real execution could produce.

The corresponding cut is inconsistent: the receive of $m$ by $p 2$ is in the future of the cut, but the send of $m$ by $p 1$ is in the past. This violates the consistency condition.^[1]

Reachability theorem

Chandy and Lamport proved that any consistent global state recorded during an execution is reachable from the initial state of that execution, and the actual state of the system at the time recording completes is reachable from the recorded consistent global state.^[1] Formally, if $S 0$ is the initial state, $S$ the consistent global state recorded by the algorithm, and $S'$ the actual state when recording finishes, then $S 0$ can reach $S$ and $S$ can reach $S'$ in the system's execution order.

The recorded state need not coincide with any state that simultaneously existed during execution, but it represents a valid intermediate state through which a possible execution of the system could have passed.^[2]^[3] This property makes the recorded state reliable for checking system properties (such as whether a deadlock exists) without freezing or pausing execution.

Stable predicates

A predicate $Φ$ on global states is stable if $Φ(S)$ = true implies $Φ(S')$ = true for every global state $S'$ reachable from $S$ .^[1]^[3] Deadlock, a condition in which no process can make progress, is stable; once all processes are blocked in a wait-for cycle, no unilateral action can break it. Termination, a condition in which all processes have halted and all channels are empty, is similarly stable. Garbage-collection eligibility, the condition that no live process holds a reference to a given object, is stable across the heap states of all processes.^[4]

By the reachability theorem, if a stable predicate $Φ$ holds in a recorded consistent global state $S$ , it holds in the actual current state $S'$ , because $S'$ is reachable from $S$ and stability guarantees $Φ$ cannot become false along any reachable path.^[1]^[2] A snapshot algorithm can therefore detect stable conditions without interrupting execution.

Unstable predicates, those that can become false after becoming true, cannot be reliably evaluated from a single snapshot. Detecting transient conditions such as whether a particular message is currently in transit requires continuous monitoring or multiple observations, outside the scope of snapshot-based techniques.^[3]

Recording a global state

Recording a consistent global state requires a coordinated protocol because messages may be in transit when local states are collected; an uncoordinated collection can produce an inconsistent cut.^[1] Any correct protocol must guarantee that the set of recorded local states and channel contents satisfies the consistency condition.

The marker-based protocol of Chandy and Lamport (1985) proceeds as follows.^[1] The initiating process records its own local state and sends a special control message, a marker, on every outgoing channel before sending any further application messages on those channels. When a process $p i$ receives a marker on channel $c ji$ for the first time, it records its own local state, records the state of $c ji$ as empty, and sends a marker on all its own outgoing channels. Messages received on any incoming channel $c ki$ after $p i$ 's state is recorded but before the marker arrives on $c ki$ are recorded as the state of that channel. The algorithm terminates when every process has received a marker on all incoming channels; the collected local states and channel states form a consistent global state.^[1]^[2]

The marker-based protocol assumes FIFO channel ordering. For systems with non-FIFO channels, the Lai–Yang algorithm (1987) uses message colouring, tagging each application message as pre-snapshot or post-snapshot, to avoid the need for explicit markers.^[5] Mattern's algorithm (1989) uses vector clocks to determine which messages belong to which snapshot, enabling multiple concurrent snapshots without dedicated marker messages.^[6]

Applications

Consistent global states, and the stable-predicate property they support, have been applied across distributed systems research and practice.^[1]^[4]

Deadlock detection. A distributed deadlock is a cycle of processes each waiting for a resource held by the next; this is a stable property. Recording a consistent global state and checking the recorded wait-for graph for cycles detects deadlock without false negatives: if a cycle exists in the recorded state, it exists in the actual current state by stability.^[1]^[2]

Termination detection. Termination, no process active and no messages in transit, is stable. A consistent global snapshot in which all process states are idle and all channel states are empty confirms that the computation has finished.^[3]^[4]

Distributed garbage collection. An object with no live references is eligible for collection; this property is stable across the combined heap states of all processes. Snapshot-based garbage collectors identify unreachable objects by recording a consistent global state of all process heaps.^[4]

Checkpointing and rollback recovery. Periodically recording consistent global states creates recovery points from which execution can restart after a process failure, without replaying the full execution from the beginning. The reachability theorem guarantees that restarting from a recorded consistent state leads to a valid continuation.^[4]^[2]

Distributed debugging. Assertion violations and invariant failures are stable if framed as conditions that, once triggered, are not automatically cleared. Replaying recorded consistent global states allows a debugger to check whether such conditions held during an execution.^[4]

Extensions

Subsequent work has relaxed the assumptions of the original Chandy–Lamport model.^[3]^[4]

Non-FIFO channels. The original protocol requires channels to deliver messages in order. Lai and Yang (1987) extended snapshot recording to non-FIFO channels by colouring messages: each process colours all application messages it sends after recording its own state with a post-snapshot colour, allowing receivers to distinguish pre-snapshot from post-snapshot messages without markers.^[5] Mattern (1989) achieved a similar result using vector clocks, which provide each message with a timestamp sufficient to determine its relationship to the snapshot without explicit colouring or markers.^[6]

Systems with process failures. If a process fails during snapshot recording, its local state cannot be captured; messages in transit on channels to or from the failed process may never be delivered. Coordinated checkpointing protocols and message-logging schemes extend snapshot recording for fault-tolerant systems by combining local state recording with logging of sent and received messages, enabling recovery even when some recorded states are lost.^[3]^[4]

Dynamic process sets. Variants exist for systems in which processes may join or leave the computation during execution. These protocols track process membership as part of the snapshot, recording which processes existed at the time of each local state observation.^[3]

References

↑ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 Chandy, K. Mani; Lamport, Leslie (February 1985). "Distributed snapshots: Determining global states of distributed systems". ACM Transactions on Computer Systems. 3 (1): 63–75. doi:10.1145/214451.214456.
↑ ^2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 Lynch, Nancy A. (1996). Distributed Algorithms. San Francisco: Morgan Kaufmann. ISBN 978-1-55860-348-6. Search this book on
↑ ^3.00 ^3.01 ^3.02 ^3.03 ^3.04 ^3.05 ^3.06 ^3.07 ^3.08 ^3.09 Tel, Gerard (2001). Introduction to Distributed Algorithms (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-79483-1. Search this book on
↑ ^4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 Ghosh, Sukumar (2014). Distributed Systems: An Algorithmic Approach (2nd ed.). Boca Raton: CRC Press. ISBN 978-1-4665-5298-2. Search this book on
↑ ^5.0 ^5.1 Lai, Ten-Hwang; Yang, Tao H. (June 1987). "On distributed snapshots". Information Processing Letters. 25 (3): 153–158. doi:10.1016/0020-0190(87)90008-7.
↑ ^6.0 ^6.1 Mattern, Friedemann (1989). "Virtual time and global states of distributed systems". Parallel and Distributed Algorithms. North-Holland. pp. 215–226. Search this book on

This article "Global state (computer science)" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Global state (computer science). Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

[ChandyLamport1985-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 Chandy, K. Mani; Lamport, Leslie (February 1985). "Distributed snapshots: Determining global states of distributed systems". ACM Transactions on Computer Systems. 3 (1): 63–75. doi:10.1145/214451.214456.

[LynchBook-2] 2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 Lynch, Nancy A. (1996). Distributed Algorithms. San Francisco: Morgan Kaufmann. ISBN 978-1-55860-348-6. Search this book on

[TelBook-3] 3.00 ^3.01 ^3.02 ^3.03 ^3.04 ^3.05 ^3.06 ^3.07 ^3.08 ^3.09 Tel, Gerard (2001). Introduction to Distributed Algorithms (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-79483-1. Search this book on

[GhoshBook-4] 4.0 ^4.1 ^4.2 ^4.3 ^4.4 ^4.5 ^4.6 ^4.7 ^4.8 Ghosh, Sukumar (2014). Distributed Systems: An Algorithmic Approach (2nd ed.). Boca Raton: CRC Press. ISBN 978-1-4665-5298-2. Search this book on

[LaiYang1987-5] 5.0 ^5.1 Lai, Ten-Hwang; Yang, Tao H. (June 1987). "On distributed snapshots". Information Processing Letters. 25 (3): 153–158. doi:10.1016/0020-0190(87)90008-7.

[Mattern1989-6] 6.0 ^6.1 Mattern, Friedemann (1989). "Virtual time and global states of distributed systems". Parallel and Distributed Algorithms. North-Holland. pp. 215–226. Search this book on

[1]

[2]

[3]

[4]

[5]

[6]