CS8603:Distributed Systems Department of CSE
2020 – 2021 2.
6
Jeppiaar Institute of Technology
• Examples: In Figure
6.5
(a-c) using a timing diagram, will deadlock if run with
synchronous primitives.
Figure 6.5 Illustrations of asynchronous executions and of crowns. (a) Crown of size 2. (b) Another crown of size 2. (c) Crown of
size 3.
2.3 Executions realizable with synchronous communication (RSC)
• In an A-execution, the messages can be made to appear instantaneous if there exists a
linear extension of the execution, such that each send event is immediately followed by
its corresponding receive event. Such an A-execution that is realized under synchronous
communication is called a realizable with synchronous communication (RSC)
execution.
Non-separated linear extension: A non-separated linear extension of (E,
≺) is a linear
extension of (E,
≺) such that for each pair (s, r) ∈ T, the interval { x ∈ E | s ≺ x ≺ r} is empty.
Example:
(CO Executions)
• In the above figure:
, r
2
, s
3
, r
3
, s
1
, r
1
> is a linear extension that is non separated.
, s
1
, r
2
, s
3
, r
3
, s
1
> is a linear extension that is separated.
RSC execution: An A-execution (E,
≺) is an RSC execution if and only if there exists a
non-separated linear extension of the partial order (E,
≺).
Crown : Let E be an execution. A crown of size k in E is a sequence
<(s
i
, r
i
), i
∈ {0, ..., k−1}> of pairs of corresponding send and receive events
such that: s0
≺ r
1
, s
1
≺ r
2
,... , s
k−2
≺ r
k−1
, s
k−1
≺ r
0
.
• On the set of messages T, we define an ordering ↪ such that m ↪ mꞌ if and only if s ≺
rꞌ.
Chia sẻ với bạn bè của bạn: |
