CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
1
Jeppiaar Institute of Technology
UNIT II - MESSAGE ORDERING & SNAPSHOTS
Message ordering and group communication: Message ordering paradigms –
Asynchronous execution with synchronous communication –Synchronous program order
on an asynchronous system –Group communication – Causal order (CO) – Total order.
Global state and snapshot recording algorithms: Introduction –System model and
definitions –Snapshot algorithms for FIFO channels
Message Ordering and Group Communication
• For any two events a and b, where each can be either a send or a receive event, the
notation
• a ~ b denotes that a and b occur at the same process, i.e., a ∈ E
i
and b
∈ E
i
for some
process i. The send and receive event pair for a message called pair of
corresponding
events.
• For a given execution E, let the set of all send–receive
event pairs be denoted as
• 𝒯 = {(s,r) ∈ E
i
× E
j
| s corresponds to r}.
2.1 Message ordering paradigms
• Distributed program logic greatly depends on the order of delivery of messages.
• Several orderings on messages have been defined: (i) non-FIFO, (ii) FIFO, (iii) causal
order, and (iv) synchronous order.
Asynchronous executions
Definition 6.1 (A-execution): An asynchronous execution (or A-execution) is an
execution (E,≺) for which the causality relation is a partial order.
• On a logical link between two nodes (is formed as multiple paths may exist) in the
system, if the messages are delivered in any order then
it is known as non-FIFO
executions. Example: IPv4.
• Each physical link delivers the messages sent on it in FIFO order due to the physical
properties of the medium.
( Illustrating FIFO and non-FIFO executions. (a) An A-execution that is not a FIFO execution. (b) An A-execution that
is also a FIFO execution.)
