Distributed Computing (2008)
756 pág.

Distributed Computing (2008)


DisciplinaAlgorítimos Distribuídos32 materiais283 seguidores
Pré-visualização50 páginas
rule\u201d
else
Record the state of C as the set of messages
received along C after pj,s state was recorded
and before pj received the marker along C
Algorithm 4.1 The Chandy\u2013Lamport algorithm.
95 4.3 Snapshot algorithms for FIFO channels
distinguished by using unique markers. Different initiations by a process are
identified by a sequence number.
Correctness
To prove the correctness of the algorithm, we show that a recorded snapshot
satisfies conditions C1 and C2. Since a process records its snapshot when it
receives the first marker on any incoming channel, no messages that follow
markers on the channels incoming to it are recorded in the process\u2019s snapshot.
Moreover, a process stops recording the state of an incoming channel when
a marker is received on that channel. Due to FIFO property of channels, it
follows that no message sent after the marker on that channel is recorded in
the channel state. Thus, condition C2 is satisfied. When a process pj receives
message mij that precedes the marker on channel Cij , it acts as follows: if
process pj has not taken its snapshot yet, then it includes mij in its recorded
snapshot. Otherwise, it records mij in the state of the channel Cij . Thus,
condition C1 is satisfied.
Complexity
The recording part of a single instance of the algorithm requiresO\ufffde\ufffdmessages
and O\ufffdd\ufffd time, where e is the number of edges in the network and d is the
diameter of the network.
4.3.2 Properties of the recorded global state
The recorded global state may not correspond to any of the global states that
occurred during the computation. Consider two possible executions of the
snapshot algorithm (shown in Figure 4.3) for the money transfer example of
Figure 4.2:
Figure 4.3 Timing diagram of
two possible executions of the
banking example.
$50
$0$0C21
C12 $0 $50
$630$630
$50
$80
$80
$170$120$120
$550$550$600
$0
$0$50
$0
t0 t1 t2 t3 t4
Markers
(2nd example)
Markers
(1st example)
Execution
Message
$200$200
S1:A
S2:B
96 Global state and snapshot recording algorithms
1. (Markers shown using dashed-and-dotted arrows.) Let site S1 initiate the
algorithm just after t1. Site S1 records its local state (account A= $550)
and sends a marker to site S2. The marker is received by site S2 after
t4. When site S2 receives the marker, it records its local state (account
B= $170), the state of channel C12 as $0, and sends a marker along channel
C21. When site S1 receives this marker, it records the state of channel
C21 as $80. The $800 amount in the system is conserved in the recorded
global state,
A= $550\ufffdB = $170\ufffdC12 = $0\ufffdC21 = $80\ufffd
2. (Markers shown using dotted arrows.) Let site S1 initiate the algorithm
just after t0 and before sending the $50 for S2. Site S1 records its local
state (account A = $600) and sends a marker to site S2. The marker is
received by site S2 between t2 and t3. When site S2 receives the marker, it
records its local state (account B = $120), the state of channel C12 as $0,
and sends a marker along channel C21. When site S1 receives this marker,
it records the state of channel C21 as $80. The $800 amount in the system
is conserved in the recorded global state,
A= $600\ufffdB = $120\ufffdC12 = $0\ufffdC21 = $80\ufffd
In both these possible runs of the algorithm, the recorded global states never
occurred in the execution. This happens because a process can change its state
asynchronously before the markers it sent are received by other sites and the
other sites record their states.
Nevertheless, as we discuss next, the system could have passed through the
recorded global states in some equivalent executions. Suppose the algorithm
is initiated in global state Si and it terminates in global state St. Let seq be the
sequence of events that takes the system from Si to St. Let S
\u2217 be the global
state recorded by the algorithm. Chandy and Lamport [6] showed that there
exists a sequence seq\u2032 which is a permutation of seq such that S\u2217 is reachable
from Si by executing a prefix of seq
\u2032 and St is reachable from S\u2217 by executing
the rest of the events of seq\u2032.
A brief sketch of the proof is as follows: an event e is defined as a pre-
recording/post-recording event if e occurs on a process p and p records its
state after/before e in seq. A post-recording event may occur after a pre-
recording event only if the two events occur on different processes. It is shown
that a post-recording event can be swapped with an immediately following
pre-recording event in a sequence without affecting the local states of either
of the two processes on which the two events occur. By iteratively applying
this operation to seq, the above-described permutation seq\u2032 is obtained. It
is then shown that S\u2217, the global state recorded by the algorithm for the
processes and channels, is the state after all the pre-recording events have
been executed, but before any post-recording event.
97 4.4 Variations of the Chandy\u2013Lamport algorithm
Thus, the recorded global state is a valid state in an equivalent execution
and if a stable property (i.e., a property that persists such as termination or
deadlock) holds in the system before the snapshot algorithm begins, it holds
in the recorded global snapshot. Therefore, a recorded global state is useful
in detecting stable properties.
A physical interpretation of the collected global state is as follows: consider
the two instants of recording of the local states in the banking example.
If the cut formed by these instants is viewed as being an elastic band and if
the elastic band is stretched so that it is vertical, then recorded states of all
processes occur simultaneously at one physical instant, and the recorded
global state occurs in the execution that is depicted in this modified space\u2013
time diagram. This is called the rubber-band criterion. For example, consider
the two different executions of the snapshot algorithm, depicted in Figure 4.3.
For the execution for which the markers are shown using dashed-and-dotted
arrows, the instants of the local state recordings are marked by squares.
Applying the rubber-band criterion, these can be stretched to be vertical or
instantaneous. Similarly, for the other execution for which the markers are
shown using dotted arrows, the instants of local state recordings are marked
by circles. Note that the system execution would have been like this, had the
processors\u2019 speeds and message delays been different. Yet another physical
interpretation of the collected global state is as follows: all the recorded
process states are mutually concurrent \u2013 no recorded process state causally
depends upon another. Therefore, logically we can view that all these process
states occurred simultaneously even though they might have occurred at
different instants in physical time.
4.4 Variations of the Chandy\u2013Lamport algorithm
Several variants of the Chandy\u2013Lamport snapshot algorithm followed.
These variants refined and optimized the basic algorithm. For example, the
Spezialetti and Kearns algorithm [29] optimizes concurrent initiation of snap-
shot collection and efficiently distributes the recorded snapshot. Venkatesan\u2019s
algorithm [32] optimizes the basic snapshot algorithm to efficiently record
repeated snapshots of a distributed system that are required in recovery algo-
rithms with synchronous checkpointing.
4.4.1 Spezialetti\u2013Kearns algorithm
There are two phases in obtaining a global snapshot: locally recording the
snapshot at every process and distributing the resultant global snapshot to
all the initiators. Spezialetti and Kearns [29] provided two optimizations
to the Chandy\u2013Lamport algorithm. The first optimization combines snap-
shots concurrently initiated by multiple processes into a single snapshot. This
98 Global state and snapshot recording algorithms
optimization is linked with the second optimization, which deals with the