Distributed Systems: Global States

Distributed Systems
Global States
Detecting global properties
We want to find out whether a particular property is true of a
distributed system as it executes.
We will see three examples:
Distributed garbage collection: if there are no longer any
reference to objects anywhere in the distributed system, the
memory taken up by the objects should be reclaimed.
Distributed deadlock detection: when each of a collection of

processes waits for another process to send it a message, and
where there is a cycle in the graph of this “wait-for” relationship.
Distributed termination detection: detect if a distributed

algorithm has terminated. It seems that we only need to test
whether each process has halted. However, it is not true.
Detecting global properties
p1 p2
object
reference
message
a. Garbage collection garbage object
p1 p2
wait-for
b. Deadlock wait-for
p1 p2
activate
c. Termination passive passive
Global States and consistent cuts
It is possible to observe the succession of states of an individual

process, but the question of how to ascertain a global state of the
system – the state of the collection of processes is much harder.
The essential problem is the absence of global time. If we had

perfectly synchronized clocks at which processes would record its
state, we can assemble the global state of the system from local
states of all processes at the same time.
The question is: can we assemble the global state of the system
from local states recorded at different real times?
The answer is “YES”.

Some definitions
history ( pi ) = hi =< ei0 , ei1 , ei2 ,... >

finite prefix of history : hik =< ei0 , ei1 , ei2 ,...eik >
A series of events occurs at each process. Each event is either an
internal action of the process (variables updates) or it is the sending
or receipt of a message over the channel.
is the state of process Pi before kth event occurs, so is

the initial state of Pi.
Thus the global state corresponds to initial prefixes of the individual

process histories.
Cuts
0 1 2 3
e1 e1 e1 e1
p1
m1 m2
Physical
p2
0 1 2 time
e2 e2 e2
Inconsistent cut Consistent cut
A cut of the system’s execution is a subset of its global history that is a union
of prefixes of process histories.
C = h1c1 ∪ h2c2 ∪ ... ∪ hNcN

The state of each process is in the state after the last event occurs in its own
cut. The set of last events from all processes are called frontier of the cut.
Cuts
0 1 2 3
e1 e1 e1 e1
p1
m1 m2
Physical
p2
0 1 2 time
e2 e2 e2
Inconsistent cut Consistent cut
• Inconsistent cut: since P2 contains receiving of m1, but at P1 it

does not include sending of that message. This cut shows the an
effect without a cause. We will never reach a global state that
corresponds to process state at the frontier by actual execution
under this cut.
• Consistent cut: it includes both the sending and receipt of m1. It
includes the sending but not the receipt of m2. It is still consistent
with actual execution.
Consistent cut
• A cut C is consistent if, for each event it contains, it also

contains all the events that happened-before that event.
for all events e ∈ C , f → e ⇒ f ∈ C
• A consistent global state is one that corresponds to a

consistent cut.
• A run is a total ordering of all the events in a global
history that is consistent with each local history’s
ordering.
• A linearization or consistent run is an ordering of the
events in a global history that is consistent with this
happened-before relation.
Global state predicate
• Global state predicate is a function that maps from the set
of global states of processes n the system to true or false.
• Stable characteristics associated with object being

garbage, deadlocked or terminated: once the system
enters a state in which the predicate is True. It remains
True in all future states reachable from that state.
• Safety (evaluates to deadlocked false for all states

reachable from S0)
• Liveness ( evaluate to reaching termination true for some

of the states reachable from S0)
Chandy and Lamport’s ‘snapshot’
algorithm
• Chandy and Lamport(1985) describe a “snapshot”
algorithm for determining global states of distributed
system.
• Record a set of process and channel states for a set of

processes Pi such that even though the combination of
recorded states may never have occurred at the same
time, the recorded global state is consistent.
• The algorithm records state locally at processes without

giving a method for gathering the global state.
Assumption of Snapshot Algorithm
1. Neither channels nor processes fail; communication is

reliable so that every message sent is eventually received
intact, exactly once;
2. Channel are unidirectional either incoming or outgoing
and provide FIFO order message delivery;
3. The graph of processes and channels is strongly
connected (there is a path between any two processes).
4. Any process may initiate a global snapshot at any time.
5. The processes may continue their normal execution and
send and receive normal massages while the snapshot
takes place.
Snapshots Ideas
• Each process records its own state and also for each
incoming channel a set of messages sent to it.
• Allow us to record process states at different times but to

account for the differential between process states in terms
of message transmitted but not yet received.
• If process pi has sent a message m to process pj, but pj

has not received it, then we account for m as belong to the
state of the channel between them.
Chandy and Lamport’s ‘snapshot’
algorithm
Use of special marker message. It has a dual role, as a prompt for the receiver
to save its own state if it has not done so; and as a means of determining which
messages to include in the channel state.
******************************************************************
Marker receiving rule for process pi
On pi’s receipt of a marker message over channel c:
if (pi has not yet recorded its state) it
records its process state now;
records the state of c as the empty set;
turns on recording of messages arriving over other incoming channels;
else
pi records the state of c as the set of messages it has received over c
since it saved its state.
end if
Marker sending rule for process pi
After pi has recorded its state, for each outgoing channel c:
pi sends one marker message over c
(before it sends any other message over c).
Two processes and their initial states
14
p1 c2 p2
c1
$1000 (none) $50 2000
account widgets account widgets
Two processes connected by two unidirectional channels, c1 and c2. The two
processes trade in ‘widgets’. Process p1 sends orders for widgets over c2 to p2,
enclosing payment at the rate of $10 per widget. Some time later, process p2
sends widgets along channel c1 to p1.
Process p2 already received an order for five widgets, which it will shortly
dispatch to p1.
The execution of the processes
1. Global state S 0
<$1000, 0> p1 c2 (empty) p2 <$50, 2000>
c1 (empty)
2. Global state S 1 Final recorded state

<$900, 0> p1 c2 (Order 10, $100), M p2 <$50, 2000>
is:
c1 (empty) P1<$1000,0>
3. Global state S2 P2<$50,1995>
<$900, 0> p1 c2 (Order 10, $100), M p2 <$50, 1995>
C1<five widgets>
c1 (five widgets)
C2<>
4. Global state S3
<$900, 5> p1 c2 (Order 10, $100) p2 <$50, 1995>
c1 (empty)
(M = marker message)
1. P1 records its state in S0. Following the marker sending rule, it will send a
marker over c2 to p2 before it sends the next order (10, $100). 2. Before p2
receives the marker, it sends five widgets to p1 over c1. 3. Now P1 receives five
widgets and P2 receives marker. P2 will record it state S2 and record c2 as
empty. Following the sending rule, p2 sends a marker to p1. 4. P1 receives the
marker, P1 records the state of c1 as five widget that it received after it first
recorded its state.
Chandy-Lamport Algorithm Proof
Theorem: The Chandy-Lamport Algorithm terminates
– Proof:
•Assumption: a process receiving a marker message will
record its state and send marker messages via each
outgoing channel in finite period of time.
•If there is a communication path from P_i to P_k, then P_k
will record its state a finite period of time after P_i
•Since the communication graph is strongly connected, all
process in the graph will have terminated recording their
state and the state of incoming channels a finite time after
some process initiated snapshot taking.
Chandy-Lamport Algorithm Proof
Theorem: Snapshots taken by the Chandy-Lamport Algorithm correspond
to consistent global states
Proof:
Let e_i and e_k be events at P_i and P_k, and let e_i → e_k.
Then, if e_k is in the cut, so is e_i.
That means, if e_k occurred before P_k recorded its state, then e_i must
have
occurred before P_i recorded its state
k=i: obvious.
k≠i: assume P_i recorded its state before e_i occurred
- as k≠i there must be a finite sequence of messages
m_1,..., m_n that induced e_i → e_k
- then, before any of the m_1,..., m_n had arrived, a
marker
must have arrived at P_k , and P_k must have recorded
it’s
state before e_k occurred, hence a contradiction to the
above assumption
Summary
• Global state
• Consistent cut and inconsistent cut
• Global state predicate
• Stability, safety and liveness
• Snapshot algorithm of Chandy lamport

Distributed Systems: Global States

Uploaded by

Copyright:

Available Formats

Distributed Systems: Global States

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Distributed Systems: Global States

Uploaded by

Copyright:

Available Formats

Distributed Systems

Distributed deadlock detection: when each of a collection of

Distributed termination detection: detect if a distributed

It is possible to observe the succession of states of an individual

The essential problem is the absence of global time. If we had

The answer is “YES”.

history ( pi ) = hi =< ei0 , ei1 , ei2 ,... >

is the state of process Pi before kth event occurs, so is

Thus the global state corresponds to initial prefixes of the individual

Inconsistent cut Consistent cut

C = h1c1 ∪ h2c2 ∪ ... ∪ hNcN

Inconsistent cut Consistent cut

• Inconsistent cut: since P2 contains receiving of m1, but at P1 it

• A cut C is consistent if, for each event it contains, it also

• A consistent global state is one that corresponds to a

• Stable characteristics associated with object being

• Safety (evaluates to deadlocked false for all states

• Liveness ( evaluate to reaching termination true for some

• Record a set of process and channel states for a set of

• The algorithm records state locally at processes without

1. Neither channels nor processes fail; communication is

• Allow us to record process states at different times but to

• If process pi has sent a message m to process pj, but pj

$1000 (none) $50 2000

account widgets account widgets

2. Global state S 1 Final recorded state

• Consistent cut and inconsistent cut

• Global state predicate

• Stability, safety and liveness

• Snapshot algorithm of Chandy lamport

You might also like