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

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   10   ...   19
c5 cacdacdiemhtttdl
Algorithm for binary rendezvous 
Each process, has a set of tokens representing the current interactions that are enabled 
locally. If multiple interactions are enabled, a process chooses one of them and tries to 
“synchronize” with the partner process. 
• The scheduling messages must satisfying the following constraints: 
o Schedule on-line, atomically, and in a distributed manner. 
o Schedule in a deadlock-free manner (i.e., crown-free), such that both the sender 
and receiver are enabled for a message when it is scheduled. 

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
Jeppiaar Institute of Technology
o Schedule to satisfy the progress property (i.e., find a schedule within a bounded 
number of steps) in addition to the safety (i.e., correctness) property. 
• Additional features of a good algorithm are: 
symmetry or some form of fairness, i.e., not favoring particular processes 
efficiency, i.e., using as few messages as possible 
• A simple algorithm by Bagrodia, makes the following assumptions: 
1. Receive commands are forever enabled from all processes. 
2. A send command, once enabled, remains enabled until it completes. 
3. To prevent deadlock, process identifiers are used to break the crowns. 
4. Each process attempts to schedule only one send event at any time. 
• The algorithm illustrates how crown-free message scheduling is achieved on-line. 
Messages used to implement synchronous order. P

has higher priority than P

. (a) P

issues SEND(M). 
(b) P

issues SEND(M). 
• The message types used are: 
(i) M – Message is the one i.e., exchanged between any two process during execution 
(ii) ack(M) – acknowledgment for the received message M 
(iii) request(M) – when low priority process wants to send a message M to the high 
priority process it issues this command. 
(iv) permission(M) – response to the request(M) to low priority process from the high 
priority process. 
(Examples showing how to schedule messages sent with synchronous primitives) 
• A cyclic wait is prevented because before sending a message M to a higher priority 
process, a lower priority process requests the higher priority process for permission to 
synchronize on M, in a non-blocking manner. 
• While waiting for this permission, there are two possibilities: 
1. If a message M′ from a higher priority process arrives, it is processed by 

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   10   ...   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