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

CS8603:Distributed Systems Department of CSE

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
(6.2 a) Not a CO execution. 
Definition (Empty-interval execution) An execution (E,≺) is an empty-interval (EI) 
execution if for each pair of events (s, r) 
∈ 𝒯, the open interval set {x ∈ E | s ≺ x 
≺ r} in the partial order is empty. 
Example Consider any message, say m
, in Figure 
(b). There does not exist any 
event x such that s

≺ x ≺ r
. This holds for all messages in the execution. Hence, the 
execution is EI. 
Figure: CO Execution 
Corollary: An execution (E,
≺) is CO if and only if for each pair of events (s,r) ∈ 𝒯 and each 
event e 
∈ E, 
• weak common past: e ≺ r ⇒ ¬(s ≺ e) 
• weak common future: s ≺ e ⇒ ¬(e ≺ r)
2.2 Synchronous execution (SYNC) 
• When all the communication between pairs of processes uses synchronous send and 
receive primitives, the resulting order is the synchronous order. 
• As each synchronous communication involves a handshake between the receiver and 
the sender, the corresponding send and receive events can be viewed as occuring 
instantaneously and atomically. 
In a timing diagram, the “instantaneous” message communication can be shown by 
bidirectional vertical message lines. 
• The “instantaneous communication” property of synchronous executions requires that 
two events are viewed as being atomic and simultaneous, and neither event precedes 
the other. 
Definition (Causality in a synchronous execution) The synchronous causality 
≪ on E is the smallest transitive relation that satisfies the following: 

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