Chapter 2: A Model of Distributed

Computations
Ajay Kshemkalyani and Mukesh Singhal

Distributed Computing: Principles, Algorithms, and Systems

Cambridge University Press

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 1/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Distributed Program

A distributed program is composed of a set of n asynchronous processes,

p1, p2, ..., pi , ..., pn .
The processes do not share a global memory and communicate solely
by passing messages.
The processes do not share a global clock that is instantaneously accessible
to these processes.
Process execution and message transfer are asynchronous.
Without loss of generality, we assume that each process is running on a
different processor.
Let Cij denote the channel from process pi to process pj and let mij denote a
message sent by pi to pj .
The message transmission delay is finite and unpredictable.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 2/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

The execution of a process consists of a sequential execution of its actions.

The actions are atomic and the actions of a process are modeled as three
types of events, namely, internal events, message send events, and message
receive events.
Let eix denote the x th event at process
pi . a message m, let send (m) and rec (m) denote its send and receive
For
events, respectively.
The occurrence of events changes the states of respective processes and
channels.
An internal event changes the state of the process at which it occurs.
A send event changes the state of the process that sends the message
and the state of the channel on which the message is sent.
A receive event changes the state of the process that receives the
message and the state of the channel on which the message is received.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 3/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

The events at a process are linearly ordered by their order of

occurrence.
The execution of process pi produces a sequence of events ei1, e2i , ..., ex ,
eix+1, ... and is denoted by Hi where i

H i = (hi , → i )
hi is the set of events produced by pi and
binary relation →i defines a linear order on these events.
Relation → i expresses causal dependencies among the events
of pi .

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 4/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

The send and the receive events signify the flow of information between
processes and establish causal dependency from the sender process to the
receiver process.
A relation →msg that captures the causal dependency due to message
exchange, is defined as follows. For every message m that is exchanged
between two processes, we have
send (m) → msg rec (m).
Relation →msg defines causal dependencies between the pairs of
corresponding send and receive events.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 5/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

The evolution of a distributed execution is depicted by a space-time diagram.

A horizontal line represents the progress of the process; a dot indicates
an event; a slant arrow indicates a message transfer.
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 the Figure 2.1, 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.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 6/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

e11 e12 e13 e14 e5

1
p
1

e21 e22 e23 e24 e26

p
2
e25
e31 e33
p
3
e32 e34
time

Figure 2.1: The space-time diagram of a distributed execution.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 7/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

Causal Precedence Relation

The execution of a distributed application results in a set of distributed
events produced by the processes.
Let H =∪i hi denote the set of events executed in a distributed
computation.
Define a binary relation → on the set H as follows that expresses
causal dependencies between events in theexdistributed execution.
i → i e i .e., (i = j ) ∧ (x <
y


 yj )
or
∀ei , ∀e
x
j
y
∈ H e, xi → e ⇔
y
eix →msg ey
j  orj


∃eez y∈k H : ex → ez i ∧ ez →
k
k
j
The causal precedence relation induces an irreflexive partial order on the
events of a distributed computation that is denoted as H=(H , →).

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 8/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

. . . Causal Precedence Relat ion

Note that the relation → is nothing but Lamport’s “happens before” relation.
For any two events ei and ej , if ei → 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-time diagram that starts at ei and ends at ej .)
For example, in Figure 2.1, e1 → e3 and e3 → e6.
1 3 3 2
The relation → denotes flow of information in a distributed computation and
ei → ej dictates that all the information available at ei is potentially
accessible at ej .
For example, in Figure 2.1, event e26 has the knowledge of all other events
shown in the figure.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 9/ 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

. . . Causal Precedence Relat ion

For any two events ei and ej , ei /→ 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 .
In this case, 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, 1e3 /→3 e3 and2 e4 /→
1. 3
Noteethe following two rules:
For any two events ei and ej , ei /→ ej /⇒
ej /→ ei . For any two events ei and ej , ei →
ej ⇒ ej /→ ei .

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 10 / 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

Concurrent events
For any two events ei and ej , if ei /→ ej and ej /→ ei ,
then events ei and ej are said to be concurrent (denoted as ei ǁ ej ).
In the execution of Figure 2.1, e3 ǁ e3 and e4 ǁ e1.
1
3
2
3
The relation ǁ is not transitive; that is, (ei ǁ ej ) ∧ (ej ǁ ek ) /⇒ ei ǁ
ek .
For example, in Figure 2.1, e3 ǁ e4 and e4 ǁ e5, however, e3 /ǁ e5.
3 2
2
1
3
1
For any two events ei and ej in a distributed execution,
ei → ej or ej → ei , or ei ǁ ej .
A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 11 / 1
 Distributed Computing: Principles, Algorithms, and Systems

A Model of Distributed Executions

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.
Two or more events may be logically concurrent even though they do
not occur at the same instant in physical time.
However, if processor speed and message delays would have 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
not, 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, we can assume that
these events occured at the same instant in physical time.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 12 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Models of Communication Networks

There are several models of the service provided by communication networks,

namely, FIFO, 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.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 13 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Models of Communication Networks

The “causal ordering” model is based on Lamport’s “happens before”

relation.
A system that supports the causal ordering model satisfies the following
property:
CO: For any two messages mij and mkj , if send (mij ) −→
send (mkj ), then rec (mij ) −→ rec (mkj ).
This property ensures that causally related messages destined to the same
destination are delivered in an order that is consistent with their causality
relation.
Causally ordered delivery of messages implies FIFO message delivery. (Note
that CO ⊂ FIFO ⊂ Non-FIFO.)
Causal ordering model considerably simplifies the design of distributed
algorithms because it provides a built-in synchronization.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 14 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Global State of a Distributed

System
“A collection of the local states of its components, namely,
the processes and the communication channels.”
The state of a process 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 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.
An internal event changes the state of the process at which it occurs.
A send event changes the state of the process that sends the message
and the state of the channel on which the message is sent.
A receive event changes the state of the process that or receives the
message and the state of the channel on which the message is received.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 15 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System

Not at ions
LSix denotes the state of process pi after the occurrence of event ex and
before
i the event eix+1.
LSi 0 denotes the initial state of process
pi .x is a result of the execution of all the events executed by process pi till ex .
LS
i
i
Let send (m)≤LSx denote the fact that ∃y :1≤y ≤x :: ey =send (m).
i i
Let rec (m)/≤LSx denote the fact that ∀y :1≤y ≤x :: ey /=rec (m).
i i

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 16 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System

A Channel State
The state of a channel depends upon the states of the processes it
connects.
Let SCx , y denote the state of a channel
ij
Cij . of a channel is defined as
The state
follows: V
SCijx, y ={ mij | send (mij ) ≤ i e
x
rec (m ) /≤ ye
} j ij
Thus, channel state SCijx,y denotes all messages that pi sent upto event ex and
which process pj had not i received until event ey .
j

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 17 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System

Global State
The global state of a distributed system is a collection of the local states
of the processes and the channels.
Notationally, global state GS is defined as,
S
i i j, k SC yj , zk }
S jk
For a global state to be GSmeaningful,
= { LS the
xi 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 if there were a global system clock that can be
instantaneously read by the processes. (However, both are impossible.)

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 18 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System
A Consistent Global State
Even if the state of all the components is not 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 a state should not violate causality – an effect should not
be present without its cause. A message cannot be received if it was not
sent.
Such states are called consistent global states and are meaningful
global states.
Inconsistent global states are not meaningful in the sense that a
S S
distributed system
A global state GS =can{ never xi be in an inconsistent
yj ,z k state. global state iff
} is a consistent
i LSi , j, k SC
jk V y
∀mij : send (m ) /≤ixLS i ij ⇔ ijx i , y rec (m ) /≤ j
ij/∈ SC
That is, m state SCyi ,z k and process state LSzk LS
j
j ij
channel must not include any
ij j
message that process pi sent after executing event eixi .

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 19 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System
An Example
Consider the distributed execution of Figure 2.2.
Figure 2.2: The space-time diagram of a distributed execution.

p e11 e21 e 13 e 14
1
m
e12 12
e22 e23 e42 m 21
p2

1
p3 e3 e 32 e 33 e 34 e 53

e41 e42
p4
time

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 20 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Global State of a Distributed

System

In Figure
2.2:
A global state GS1 = {LS 11, LS23, LS3 3, LS4 2 } is
because the state of p2 has recorded the receipt of message m12,
inconsistent
however,
the state state
A global of p1 GS
has not recorded
consisting of its send.
local states {LS 2, LS 4, LS 4, LS
2 1 2 3 4
is} consistent; all the channels are empty except C21 that
2

contains message m21.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 21 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Cuts of a Distributed Computation

“In the space-time diagram of a distributed computation, a cut is a

zigzag line joining one arbitrary point on each process line.”
A cut slices the space-time 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’s space-time diagram.
Cuts in a space-time diagram provide a powerful graphical aid in representing
and reasoning about global states of a computation.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 22 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Cuts of a Distributed
Computation
Figure 2.3: Illustration of cuts in a distributed execution.

C1 C2
e11 e21 e13 e 14
p
1

e12 e22 e23 e42

p2

1
p3 e3 e 32 e 33 e34 e53

e41 e42
p4
time

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 23 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Cuts of a Distributed
Computation

In a consistent cut, every message received in the PAST of the cut was sent
in the PAST of that cut. (In Figure 2.3, cut C2 is 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. (In Figure 2.3, cut C1 is an inconsistent cut.)

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 24 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Past and Future Cones of an

Event

Past Cone of an Event

An event ej could have been affected only by all events ei such that ei →
ej .
In this situtaion, all the information available at ei could be made accessible
at ej .
All such events ei belong to the past of ej .
Let Past(ej ) denote all events in the past of ej in a computation (H , →).
Then,

Past (ej ) = { ei |∀ei ∈ H , ei → ej } .

Figure 2.4 (next slide) shows the past of an event ej .

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 25 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Past and Future Cones of an

Event Figure 2.4: Illustration of past and future cones.

max(Past i (ej )) min(Futurei (ej ))

PAST( ej ) FUTURE( e j )
e
j

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 26 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Past and Future Cones of an

Event

Let Pasti (ej ) be the set of all those events of Past(ej ) that are on process
pi .
Pasti (ej ) is a totally ordered set, ordered by the relation →i , whose
maximal element is denoted by max (Pasti (ej )).
max (Pasti (ej )) is the latest event at process pi that affected event ej
(Figure 2.4).

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 27 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Past and Future Cones of an

Event
S
Let Max Past (ej ) = (∀i ) { max (Past i (ej ))} .
Max Past(ej ) consists of the latest event at
every process that affected event
ej and is referred to as the surface of the past
cone of ej .
Past(ej ) represents all events on the past light
cone that affect ej .
Future Cone of an Event
The future of an event ej , denoted by Future(ej ), contains all events ei
that are causally affected by ej (see Figure 2.4).
In a computation (H , →), Future(ej ) is defined as:
Future(ej ) = { ei |∀ei ∈ H , ej → ei } .

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 28 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . Past and Future Cones of an

Event

Define Futurei (ej ) as the set of those events of Future(ej ) that are on
process
pi.
define min(Futurei (ej )) asSthe first event on process pi that is affected by
Define
ej. Min Future(ej ) as (∀i ) { min(Futurei (ej ))} ,
which consists of the first
event at every process that is causally affected by
event ej .
Min Future(ej ) is referred to as the surface of the
future cone of ej .
All events at a process pi that occurred after max
(Past i (ej )) but before
min(Futurei (ej )) are concurrent with ej .
Therefore, all and only those events of computation H that belong to the set
“H − Past(ej ) − Future(ej )” are concurrent with event ej .
A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 29 / 1
 Distributed Computing: Principles, Algorithms, and Systems

Models of Process Communications

There are two basic models of process communications – 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 after it learns that the receiver
process has accepted the message.
Thus, the sender and the receiver processes must synchronize to exchange
a message. On the other hand,
asynchronous communication model is a non-blocking type where the sender
and the receiver do not synchronize to exchange a message.
After having sent a message, the sender process does not wait for
the message to be delivered to the receiver process.
The message is bufferred by the system and is delivered to the
receiver process when it is ready to accept the message.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 30 / 1
 Distributed Computing: Principles, Algorithms, and Systems

. . . M odels of Process
Communications
Neither of the communication models is superior to the other.
Asynchronous communication provides higher parallelism because the sender
process can execute while the message is in transit to the receiver.
However, A buffer overflow may occur if a process sends a large number of
messages in a burst to another process.
Thus, an implementation of asynchronous communication requires more
complex buffer management.
In addition, due to higher degree of parallelism and non-determinism, it is
much more difficult to design, verify, and implement distributed algorithms
for asynchronous communications.
Synchronous communication is simpler to handle and implement.
However, due to frequent blocking, it is likely to have poor performance and
is likely to be more prone to deadlocks.

A. Kshemkalyani and M. Singhal (Distributed Comput A Model of Distributed Computations CUP 2008 31 / 1