756 pág.

# Distributed Computing (2008)

DisciplinaAlgorítimos Distribuídos28 materiais273 seguidores
Pré-visualização50 páginas
```a distributed execution
involving three processes. A horizontal line represents the progress of the
41 2.2 A model of distributed executions
Figure 2.1 The space\u2013time
diagram of a distributed
execution.
p1
p2
p3
e1
1
e2
1
e3
1 e3
3
e3
2 e3
4
e2
2 e2
3 e2
4 e2
6
e2
5
e1
2 e1
3 e1
4 e1
5
Time
process; a dot indicates an event; a slant arrow indicates a message transfer.
Generally, the execution of an event takes a finite amount of time; however,
since we assume that an event execution is atomic (hence, indivisible and
instantaneous), it is justified to denote it as a dot on a process line. In this
figure, for process p1, the second event is a message send event, the third
event is an internal event, and the fourth event is a message receive event.
Causal precedence relation
The execution of a distributed application results in a set of distributed events
produced by the processes. Let H =\u222aihi denote the set of events executed
in a distributed computation. Next, we define a binary relation on the set
H , denoted as \u2192, that expresses causal dependencies between events in the
distributed execution.
\u2200exi \ufffd \u2200eyj \u2208H\ufffd exi \u2192 eyj \u21d4
\u23a7\u23aa\u23aa\u23aa\u23aa\u23a8
\u23aa\u23aa\u23aa\u23aa\u23a9
exi \u2192i eyj i\ufffde\ufffd\ufffd \ufffdi= j\ufffd\u2227 \ufffdx < y\ufffd
or
exi \u2192msg eyj
or
\u2203ezk \u2208H \ufffd exi \u2192 ezk \u2227 ezk \u2192 eyj
The causal precedence relation induces an irreflexive partial order on the
events of a distributed computation [6] that is denoted as \ufffd=(H , \u2192).
Note that the relation \u2192 is Lamport\u2019s \u201chappens before\u201d relation [4].1 For
any two events ei and ej , if ei \u2192 ej , then event ej is directly or transitively
dependent on event ei; graphically, it means that there exists a path consisting
of message arrows and process-line segments (along increasing time) in the
space\u2013time diagram that starts at ei and ends at ej . For example, in Figure 2.1,
e11 \u2192 e33 and e33 \u2192 e62. Note that relation \u2192 denotes flow of information in a
distributed computation and ei \u2192 ej dictates that all the information available
1 In Lamport\u2019s \u201chappens before\u201d relation, an event e1 happens before an event e2, denoted
by ei \u2192 ej , if (a) e1 occurs before e2 on the same process, or (b) e1 is the send event of a
message and e2 is the receive event of that message, or (c) \u2203e\u2032 \ufffd e1 happens before e\u2032 and e\u2032
happens before e2.
42 A model of distributed computations
at ei is potentially accessible at ej . For example, in Figure 2.1, event e
6
2 has
the knowledge of all other events shown in the figure.
For any two events ei and ej , ei \ufffd\u2192 ej denotes the fact that event ej does
not directly or transitively dependent on event ei. That is, event ei does not
causally affect event ej . Event ej is not aware of the execution of ei or any
event executed after ei on the same process. For example, in Figure 2.1,
e31 \ufffd\u2192 e33 and e42 \ufffd\u2192 e13. Note the following two rules:
\u2022 for any two events ei and ej , ei \ufffd\u2192 ej \ufffd\u21d2 ej \ufffd\u2192 ei
\u2022 for any two events ei and ej , ei \u2192 ej \u21d2 ej \ufffd\u2192 ei.
For any two events ei and ej , if ei \ufffd\u2192 ej and ej \ufffd\u2192 ei, then events ei and ej are
said to be concurrent and the relation is denoted as ei \ufffd ej . In the execution
of Figure 2.1, e31 \ufffd e33 and e42 \ufffd e13. Note that relation \ufffd is not transitive; that is,
(ei \ufffd ej) \u2227 (ej \ufffd ek) \ufffd\u21d2 ei \ufffd ek. For example, in Figure 2.1, e33 \ufffd e42 and e42 \ufffd e51,
however, e33 \ufffd\ufffd e51.
Note that for any two events ei and ej in a distributed execution, ei \u2192 ej
or ej \u2192 ei, or ei \ufffd ej .
Logical vs. physical concurrency
In a distributed computation, two events are logically concurrent if and only if
they do not causally affect each other. Physical concurrency, on the other hand,
has a connotation that the events occur at the same instant in physical time.
Note that two or more events may be logically concurrent even though they
do not occur at the same instant in physical time. For example, in Figure 2.1,
events in the set {e31\ufffd e
4
2\ufffd e
3
3} are logically concurrent, but they occurred at
different instants in physical time. However, note that if processor speed and
message delays had been different, the execution of these events could have
very well coincided in physical time. Whether a set of logically concurrent
events coincide in the physical time or in what order in the physical time they
occur does not change the outcome of the computation.
Therefore, even though a set of logically concurrent events may not have
occurred at the same instant in physical time, for all practical and theoretical
purposes, we can assume that these events occured at the same instant in
physical time.
2.3 Models of communication networks
There are several models of the service provided by communication networks,
namely, FIFO (first-in, first-out), non-FIFO, and causal ordering. In the FIFO
model, each channel acts as a first-in first-out message queue and thus,
message ordering is preserved by a channel. In the non-FIFO model, a channel
acts like a set in which the sender process adds messages and the receiver
process removes messages from it in a random order. The \u201ccausal ordering\u201d
43 2.4 Global state of a distributed system
model [1] is based on Lamport\u2019s \u201chappens before\u201d relation. A system that
supports the causal ordering model satisfies the following property:
CO \ufffd For any two messages mij and mkj\ufffd if send\ufffdmij\ufffd \u2212\u2192 send\ufffdmkj\ufffd\ufffd
then rec\ufffdmij\ufffd \u2212\u2192 rec\ufffdmkj\ufffd\ufffd
That is, this property ensures that causally related messages destined to the
same destination are delivered in an order that is consistent with their causal-
ity relation. Causally ordered delivery of messages implies FIFO message
delivery. Furthermore, note that CO \u2282 FIFO \u2282 Non-FIFO.
Causal ordering model is useful in developing distributed algorithms. Gen-
erally, it considerably simplifies the design of distributed algorithms because
it provides a built-in synchronization. For example, in replicated database
systems, it is important that every process responsible for updating a replica
Without causal ordering, each update must be checked to ensure that database
consistency is not being violated. Causal ordering eliminates the need for
such checks.
2.4 Global state of a distributed system
The global state of a distributed system is a collection of the local states of its
components, namely, the processes and the communication channels [2, 3].
The state of a process at any time is defined by the contents of processor
registers, stacks, local memory, etc. and depends on the local context of the
distributed application. The state of a channel is given by the set of messages
in transit in the channel.
The occurrence of events changes the states of respective processes and
channels, thus causing transitions in global system state. For example, an
internal event changes the state of the process at which it occurs. A send event
(or a receive event) changes the state of the process that sends (or receives)
the message and the state of the channel on which the message is sent (or
Let LSxi denote the state of process pi after the occurrence of event e
x
i and
before the event ex+1i . LS
0
i denotes the initial state of process pi. LS
x
i is a
result of the execution of all the events executed by process pi till e
x
i . Let
send(m)\u2264LSxi denote the fact that \u2203y:1\u2264y\u2264x :: eyi = send(m). Likewise, let
rec(m)\ufffd\u2264LSxi denote the fact that \u2200y:1\u2264y\u2264x :: eyi \ufffd=rec(m).
The state of a channel is difficult to state formally because a channel is
a distributed entity and its state depends upon the states of the processes it
connects. Let SCx\ufffdyij denote the state of a channel Cij defined as follows:
SC
x\ufffdy
ij ={mij\ufffd send(mij) \u2264 LSxi
\u2227
rec(mij) \ufffd\u2264 LSyj }.
44 A model of distributed computations
Thus, channel state SCx\ufffdyij denotes all messages that pi sent up to event e
x
i and