Distributed Computing (2008)
756 pág.

Distributed Computing (2008)


DisciplinaAlgorítimos Distribuídos32 materiais282 seguidores
Pré-visualização50 páginas
e
y
j .
2.4.1 Global state
The global state of a distributed system is a collection of the local states of
the processes and the channels. Notationally, the global state GS is defined as
GS = {
\u22c3
iLS
xi
i ,
\u22c3
j\ufffdkSC
yj\ufffdzk
jk }.
For a global snapshot to be meaningful, the states of all the components
of the distributed system must be recorded at the same instant. This will be
possible if the local clocks at processes were perfectly synchronized or there
was a global system clock that could be instantaneously read by the processes.
However, both are impossible.
However, it turns out that even if the state of all the components in a
distributed system has not been recorded at the same instant, such a state will
be meaningful provided every message that is recorded as received is also
recorded as sent. Basic idea is that an effect should not be present without its
cause. A message cannot be received if it was not sent; that is, the state should
not violate causality. Such states are called consistent global states and are
meaningful global states. Inconsistent global states are not meaningful in the
sense that a distributed system can never be in an inconsistent state.
A global state GS = {
\u22c3
iLS
xi
i ,
\u22c3
j\ufffdkSC
yj\ufffdzk
jk } is a consistent global state iff it
satisfies the following condition:
\u2200mij \ufffd send\ufffdmij\ufffd\ufffd LSxii \u21d2mij \ufffd\u2208 SCxi\ufffdyjij \u2227 rec\ufffdmij\ufffd\ufffd LSyjj \ufffd
That is, channel state SCyi\ufffdzkik and process state LS
zk
k must not include
any message that process pi sent after executing event e
xi
i . A more rigorous
definition of the consistency of a global state is given in Chapter 4.
In the distributed execution of Figure 2.2, a global state GS1 consisting
of local states {LS11 , LS
3
2 , LS
3
3 , LS
2
4} is inconsistent because the state of p2
has recorded the receipt of message m12, however, the state of p1 has not
recorded its send. On the contrary, a global state GS2 consisting of local
Figure 2.2 The space\u2013time
diagram of a distributed
execution.
Time
m12 m21
p1
p2
p3
p4
e1
1
e2
1
e3
1
e4
1 e4
2
e3
2
e3
4 e3
5e3
3
e2
2 e2
3 e2
4
e1
2 e1
3 e1
4
45 2.5 Cuts of a distributed computation
states {LS21 , LS
4
2 , LS
4
3 , LS
2
4} is consistent; all the channels are empty except
C21 that contains message m21.
A global state GS = {
\u22c3
iLS
xi
i ,
\u22c3
j\ufffdkSC
yj\ufffdzk
jk } is transitless iff
\u2200i\ufffd\u2200j \ufffd 1\u2264 i\ufffd j \u2264 n \ufffd\ufffd SCyi\ufffdzjij = 
\ufffd
Thus, all channels are recorded as empty in a transitless global state.
A global state is strongly consistent iff it is transitless as well as consistent.
Note that in Figure 2.2, the global state consisting of local states {LS21 , LS
3
2 ,
LS43 , LS
2
4} is strongly consistent.
Recording the global state of a distributed system is an important paradigm
when one is interested in analyzing, monitoring, testing, or verifying proper-
ties of distributed applications, systems, and algorithms. Design of efficient
methods for recording the global state of a distributed system is an important
problem.
2.5 Cuts of a distributed computation
In the space\u2013time diagram of a distributed computation, a zigzag line joining
one arbitrary point on each process line is termed a cut in the computation.
Such a line slices the space\u2013time diagram, and thus the set of events in the
distributed computation, into a PAST and a FUTURE. The PAST contains all
the events to the left of the cut and the FUTURE contains all the events to the
right of the cut. For a cut C, let PAST(C) and FUTURE(C) denote the set of
events in the PAST and FUTURE of C, respectively. Every cut corresponds
to a global state and every global state can be graphically represented as a
cut in the computation\u2019s space\u2013time diagram [6].
definition 2.1 If eMax_PASTi\ufffdC\ufffdi denotes the latest event at process pi that is
in the PAST of a cut C, then the global state represented by the cut is
{
\u22c3
iLS
Max_PASTi\ufffdC\ufffd
i ,
\u22c3
j\ufffdkSC
yj\ufffdzk
jk } where SC
yj\ufffdzk
jk = {m \ufffd send(m)\u2208PAST(C) \u2227
rec(m)\u2208FUTURE(C)}.
A consistent global state corresponds to a cut in which every message
received in the PAST of the cut was sent in the PAST of that cut. Such a cut
is known as a consistent cut. All messages that cross the cut from the PAST
to the FUTURE are in transit in the corresponding consistent global state.
A cut is inconsistent if a message crosses the cut from the FUTURE to the
PAST. For example, the space\u2013time diagram of Figure 2.3 shows two cuts,
C1 and C2. C1 is an inconsistent cut, whereas C2 is a consistent cut. Note that
these two cuts respectively correspond to the two global states GS1 and GS2,
identified in the previous subsection.
46 A model of distributed computations
Figure 2.3 Illustration of cuts
in a distributed execution.
Time
C1 C2
p1
p2
p3
p4
e1
1
e2
1
e3
1
e4
1 e4
2
e3
2
e3
4 e3
5
e3
3
e2
2 e2
3 e2
4
e1
2 e1
3 e1
4
Cuts in a space\u2013time diagram provide a powerful graphical aid in repre-
senting and reasoning about global states of a computation.
2.6 Past and future cones of an event
In a distributed computation, an event ej could have been affected only by
all events ei such that ei \u2192 ej and all the information available at ei could
be made accessible at ej . All such events ei belong to the past of ej [6].
Let Past\ufffdej\ufffd denote all events in the past of ej in a computation (H , \u2192).
Then,
Past\ufffdej\ufffd= 	ei\ufffd\u2200ei \u2208H\ufffd ei \u2192 ej\ufffd.
Figure 2.4 shows the past of an event ej . Let Pasti\ufffdej\ufffd be the set of all
those events of Past\ufffdej\ufffd that are on process pi. Clearly, Pasti(ej) is a totally
ordered set, ordered by the relation \u2192i, whose maximal element is denoted
by max(Pasti(ej)). Obviously, max(Pasti(ej)) is the latest event at process
pi that affected event ej (see Figure 2.4). Note that max(Pasti(ej)) is always
a message send event.
Let Max_Past\ufffdej\ufffd =
\u22c3
\ufffd\u2200i\ufffd	max\ufffdPasti\ufffdej\ufffd\ufffd\ufffd. Max_Past\ufffdej\ufffd consists of the
latest event at every process that affected event ej and is referred to as the
Figure 2.4 Illustration of past
and future cones in a
distributed computation.
PAST(ej) FUTURE(ej)
pi
max(Pasti(ej)) min(Futurei(ej))
ej
47 2.7 Models of process communications
surface of the past cone of ej [6]. Note that Max_Past\ufffdej\ufffd is a consistent
cut [7]. Past\ufffdej\ufffd represents all events on the past light cone that affect ej .
Similar to the past is defined the future of an event. The future of an event
ej , denoted by Future\ufffdej\ufffd, contains all events ei that are causally affected by
ej (see Figure 2.4). In a computation (H , \u2192), Future\ufffdej\ufffd is defined as:
Future\ufffdej\ufffd= 	ei\ufffd\u2200ei \u2208H\ufffd ej \u2192 ei\ufffd.
Likewise, we can define Futurei\ufffdej\ufffd as the set of those events of Future\ufffdej\ufffd
that are on process pi and min(Futurei(ej)) as the first event on process pi
that is affected by ej . Note that min(Futurei(ej)) is always a message receive
event. Likewise, Min_Past\ufffdej\ufffd, defined as
\u22c3
\ufffd\u2200i\ufffd	min\ufffdFuturei\ufffdej\ufffd\ufffd\ufffd, consists
of the first event at every process that is causally affected by event ej and is
referred to as the surface of the future cone of ej [6]. It denotes a consistent
cut in the computation [7]. Future\ufffdej\ufffd represents all events on the future
light cone that are affected by ej .
It is obvious that all events at a process pi that occurred after
max\ufffdPasti\ufffdej\ufffd\ufffd but before min\ufffdFuturei\ufffdej\ufffd\ufffd are concurrent with ej . There-
fore, all and only those events of computation H that belong to the set
\u201cH\u2212Past\ufffdej\ufffd\u2212Future\ufffdej\ufffd\u201d are concurrent with event ej .
2.7 Models of process communications
There are two basic models of process communications [8] \u2013 synchronous
and asynchronous. The synchronous communication model is a blocking type
where on a message send, the sender process blocks until the message has
been received by the receiver process. The sender process resumes execution
only