These are comparison parameters for fundamental schemes of distributed mutual exclusion with overly detailed explanations and arguments. My source is the autumn 2024 course on distributed systems at ITU. Keep in mind that this is a students summary of this material.
Bandwidth
How many messages are sent to enter
and exit
the Mutex?
Solution | Comment |
---|---|
Server | Enter is 2 messages: Client sends one message to request access. Then the server sends one message to grant access when possible. Exit is 1 message sent by the client to free the Mutex. This scheme uses constant bandwidth. |
Token-ring | The token is continuously sent around to keep the system alive. This scheme uses continuous bandwidth. |
Ricart-Agrawala | Enter is \(2(N-1)\) messages: Client sends one message to every other participant to request access. Participants reply with one message to grant access. Exit is \(N-1\) messages: One message sent to all other participants to signal that the mutex is free and that others are allowed entry. This scheme uses bandwidth proportional to the number of participants. |
Client Delay
What is the minimum wait time before the client process can continue?
Solution | Comment |
---|---|
Server | The minimum Enter delay is proportional to twice the roundtrip time. \(2(\text{rt})\) Exit causes no delay as the process can do this asynchronously. |
Token-ring | The delay to Enter is proportional to between 0 (The client is already in possession of the token.) and \(N\). (The client had just released the token and must wait for a token round trip.) The average case is \(\frac{N}{2}\). The delay to exit is the time taken to send the token to the next client. (We consider the client to be in the entered state until the token is passed on.) |
Ricart-Agrawala | The minimum Enter delay is proportional to \(2(N-1)\) the time taken to contact all other participants. Exit causes no delay as the process can do this asynchronously. |
Throughput, Sync Delay
What is the minimum time between exit
of one client, and enter
of another?
Solution | Comment |
---|---|
Server | The sync. delay is proportional to twice the roundtrip time. One roundtrip from the exiting client to the server, and another from the server to the next client. |
Token-ring | The sync. delay is proportional to between 1 (The next client will enter ) and \(N\). (The same client will enter again.) The average case is \(\frac{N}{2}\). |
Ricart-Agrawala | The sync. delay is constant. The next client to enter will already have received permission from other participants in the system, and is only waiting for the one client to exit . |