Global State of a Distributed System
The global state of a distributed system is the collection of local states of its processes and communication channels.
- The state of a process is defined by registers, stacks, and local memory depending on the application context.
- The state of a channel is the set of messages currently in transit.
Global State
The global state of a distributed system is a collection of local states of processes and channels.
- Notationally, global state (GS) is defined as GS = ( ∪LS ∪ SC ).
- For a global snapshot to be meaningful, states of all components should be recorded at the same time.
- Perfect clock synchronization or a global clock is impossible.
- However, a snapshot is still meaningful if every received message is also recorded as sent.
- The main idea: no effect without cause. A message cannot be received unless it was sent.
Such states are called consistent global states. These are meaningful.
- Inconsistent states are not meaningful because a distributed system cannot exist in an inconsistent state.
Consistent Global State
A global state GS = ( ∪LS ∪ SC ) is consistent iff:
- For every message m:
send(m)∈ LS/SC ⇒rec(m)∈ LS/SC. - Channel state and process state must not include a message sent after the corresponding event.
Example:
- In one execution, GS1 with local states (LS1, LS2, LS3, LS4) is inconsistent, because process p2 recorded receipt of message m2, but p1 did not record sending it.
- Another execution, GS2 with states (LS1, LS3, LS3, LS2) is consistent; here all channels are empty except C21 which contains message m2.
Transitless Global State
A global state GS is transitless if all channels are recorded as empty.
Strongly Consistent Global State
A global state is strongly consistent if it is both:
- Consistent, and
- Transitless.
In the figure, the global state consisting of local states (LS1, LS2, LS3, LS4) is strongly consistent.
Importance of Recording Global State
Recording the global state is important for:
- Analyzing,
- Monitoring,
- Testing, and
- Verifying distributed systems, applications, and algorithms.
Designing efficient methods for recording global states is a major problem in distributed computing.
