CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
2
Jeppiaar Institute of Technology
•
In general on any logical link, messages are delivered in the order in which they are
sent.
• To implement FIFO logical channel over a non-FIFO channel, use a separate numbering
scheme to sequence the messages.
• The sender assigns and appends a
tuple to each
message. The receiver uses a buffer to order the incoming messages as per the sender’s
sequence numbers, and accepts only the “next” message in sequence.
• Figure 6.1(b) illustrates an A-execution under FIFO ordering.
2.1.2Causally ordered (CO) executions
Definition 6.3 (Causal order (CO)): A CO execution is an A-execution in which,
for all (s, r) and (s′, r′) ∈𝒯, (r ∼ r′ and s ≺ s′) ⇒ r ≺ r′.
• If two send events s and s′ are related by causality ordering then their corresponding
receive events r and r′ must occur in the same order at all common destinations.
• Figure 6.2 shows an execution that satisfies CO. s2 and s1 are related by causality but
the destinations of the corresponding messages are different. Similarly for s2 and s3.
(Fig CO executions)
• Applications of Causal order: applications that requires update to shared data, to
implement distributed shared memory, and fair resource allocation in distributed
mutual exclusion.
• Definition (causal order (CO) for implementations) If send(m
1
) ≺ send(m
2
) then
for each common destination d of messages m
1
and m
2
, deliver
d
(m
1
) ≺ deliver
d
(m
2
) must
be satisfied.
• if m
1
and m
2
are sent by the same process, then property degenerates to FIFO property.
• In a FIFO execution, no message can be overtaken by another message between the
same (sender, receiver) pair of processes.
• In a CO execution, no message can be overtaken by a chain of messages between the
same (sender, receiver) pair of processes.
• Definition (Message order (MO)): A MO execution is an A-execution in which,
for all (s, r) and (s′, r′) ∈
𝒯, s ≺ s′ ⇒ ￢(r′ ≺ r).
• Example: Consider any message pair, say m
1
and m
3
in Figure 6.2(a). s1 ≺ s3 but ￢ (r3
≺ r1) is false. Hence, the execution does not satisfy MO.
