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. 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:
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 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
(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