Lesson 4: State in Distributed Systems Flashcards
What do we need to know to understand the state of a distributed system?
- What internal events have occurred at each node
- What messages have been send and received by each node / what messages are still in flight (sent but not received)
- How the events and messages are ordered/interleaved
What tells us the global state of a distributed system?
- processes and channels
- process state defined by most recent event
- channel state defined by inflight messages
What is state? How do we keep track of it?
The state of a distributed system refers to a point in time in the execution.
The execution proceeds as a series of state transitions. The state transitions correspond to an event occurring, so we can keep track of the state transitions by keeping track of the sequence of events that trigger them.
What is a consistent cut of a distributed system?
A consistent cut is snapshot that represents a possible execution of the system with consistent ordering of events.
For example, if we have a cut where events in P3 were received but those events had not yet been sent by P1, that wouldn’t make sense. On the other hand, if we have a cut where P1 had sent events but P3 hadn’t yet received them, that would make sense and be a consistent cut b/c the events have consistent ordering.
Put another way, if an event was caused by another event, then the causal event must be included in the cut.
What is a cut of a distributed system?
A cut is a tuple where each element signifies each process’ last event that should be considered part of the snapshot state.
A cut can be consistent or inconsistent.
What is an inconsistent cut of a distributed system?
An inconsistent cut is a snapshot that represents a possible execution of the system with inconsistent order of events.
What is an inconsistent cut of a distributed system?
An inconsistent cut is a snapshot that represents a possible execution of the system with inconsistent order of events.
For example, if we have a cut where events in P3 were received but those events had not yet been sent by P1, that wouldn’t make sense.
Put another way, if an event was caused by another event, then the causal event must be included in the cut.
What is a prerecording event? What is a postrecording event?
When we capture the state of a process when trying to get to a snapshot, then all events that occurred prior to the point of time when the snapshot is taken referred to as “prerecording events” and all events that follow are referred to as “postrecording events”.
Why is it hard to capture state in a distributed system?
We don’t have a global clock, so there’s no way to tell every node to capture its state at the exact same time.
We also can’t assume that nodes can instantaneously tell each other to capture their state.
We have multiple processes executing concurrently, so at any point in time there are multiple events that can take place. This makes the overall distributed system a non-deterministic system, and reasoning about order, consistency, etc. is really hard in a non-deterministic system.
What is deterministic computation?
At any point in the computation there is at most one event that can happen next.
What is non-deterministic computation?
At any point in time in the computation there can be more than one event that can happen next.
What is the snapshot algorithm?
Chandy-Lamport algorithm
Is a recorded state a real state that the distributed system was in at some point in time?
No! It’s only a possible state! But the recorded state is reachable from the state in which the algorithm was initiated, and the state in which the algorithm terminated is reachable from the recorded state.
What is a stable property?
A property is stable if, once it becomes true, it remains true for the duration of system execution.
Examples: Deadlock, termination, token loss
What is an unstable property?
A property is unstable, if once it becomes true, there is no guarantee that it remains true for the duration of system execution.
Examples: temporary buffer overflow, load spike, race condition
