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

CS8603:Distributed Systems Department of CSE
2020 – 2021 2. 
8
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: 
(i) 
symmetry or some form of fairness, i.e., not favoring particular processes 
(ii) 
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
i 
has higher priority than P
j 
. (a) P
i 
issues SEND(M). 
(b) P
j 
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: