CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
4
Jeppiaar Institute of Technology
• S1: If x occurs before y at the same process, then x ≪ y.
• S2: If (s, r) ∈ T, then for all x ∈ E, [(x ≪ s ⇐⇒ x ≪ r) and (s ≪ x ⇐⇒ r ≪ x)].
• S3: If x ≪ y and y ≪ z, then x ≪ z.
• We can now formally define a synchronous execution.
(Figure Illustration of a synchronous communication. (a) Execution in an asynchronous system. (b) Equivalent instantaneous communication.)
Definition (S- execution): A synchronous execution is an execution (E,
≪) for which the
causality relation
≪ is a partial order.
• Timestamping a synchronous execution: An execution (E,≺) is synchronous if and
only if there exists a mapping from E to T (scalar timestamps) such that
• for any message M, T(s(M)) = T(r(M));
• for each process P
i
, if e
i
≺ e
i
′ then T(e
i
) < T(e
i
′).
Asynchronous execution with synchronous communication
• When all the communication between pairs of processes is by using synchronous
• send and receive primitives, the resulting order is synchronous order.
• A distributed program that run correctly on an asynchronous system may not be
executed by synchronous primitives. There is a possibility that the program may
deadlock, as shown by the code in Figure
6.4
.
Figure A communication program for an asynchronous system deadlocks when using synchronous
primitives.
CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
5
Jeppiaar Institute of Technology
Chia sẻ với bạn bè của bạn: |
