Unit II message ordering & snapshots message ordering and group communication: Message ordering paradigms

tải về 0.79 Mb.
Chế độ xem pdf
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
  1   2   3   4   5   6   7   8   9   ...   19
c5 cacdacdiemhtttdl

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
Jeppiaar Institute of Technology
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 
• a ~ b denotes that a and b occur at the same process, i.e., a ∈ E

and b 
∈ E

for some 
process i. The send and receive event pair for a message called pair of corresponding 
• For a given execution E, let the set of all send–receive event pairs be denoted as 
• 𝒯 = {(s,r) ∈ E

× E

| 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.) 

tải về 0.79 Mb.

Chia sẻ với bạn bè của bạn:
  1   2   3   4   5   6   7   8   9   ...   19

Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2023
được sử dụng cho việc quản lý

    Quê hương