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
trang5/19
Chuyển đổi dữ liệu15.11.2023
Kích0.79 Mb.
#55654
1   2   3   4   5   6   7   8   9   ...   19
MESSAGE ORDERING & SNAPSHOTS
c5 cacdacdiemhtttdl
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: 2
, r
2
, s
3
, r
3
, s
1
, r
1
> is a linear extension that is non separated. 
2
, 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

≺ 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ꞌ. 



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