CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
3
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
2
, in Figure
6.2
(b). There does not exist any
event x such that s
2
≺ x ≺ r
2
. 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
relation
≪ on E is the smallest transitive relation that satisfies the following:
Chia sẻ với bạn bè của bạn: |
