Ricart-Agrawala performance issues

Performance of the Ricart-Agrawala algorithm

Let N be the number of processes.

• Messages per CS entry: N−1 requests and N−1 replies = 2(N−1). This grows linearly with N, which is heavy for large systems.
• Synchronisation delay: one message time (after exit, the deferred reply reaches the waiting process).
• Response time (low load): about one round trip, 2T, plus execution time.
• Failure sensitivity: a request must be answered by all, so the crash of any one process blocks every other process; N points of failure instead of one. A crashed process can be treated as an implicit "no".
• All processes must know the full membership and keep logical clocks. Thus the algorithm is correct but expensive and fragile.

Alternate algorithm: Maekawa's voting algorithm

Idea: a process needs permission from only a subset (quorum) of processes, not all. Quorums Ri for each Pi are chosen so that any two quorums intersect (Ri ∩ Rj ≠ ∅), each of size about √N, and each process is in about √N quorums.

Algorithm:

1. To enter the CS, Pi sends REQUEST to every member of its quorum Ri.
2. A member votes (sends REPLY) for only one request at a time; if it has already voted, it queues the request (ordered by timestamp).
3. Pi enters the CS after receiving REPLY from all of Ri.
4. On exit, Pi sends RELEASE to all of Ri; each member then votes for the next queued request.

Because any two quorums share at least one member, and that member votes for only one at a time, two processes cannot both enter.

Performance: about 3√N messages (request, reply, release), against 2(N−1) for Ricart-Agrawala. Deadlock is possible (circular vote waiting); it is solved by extra messages (INQUIRE, YIELD, FAILED) using timestamps.

Another alternative is a token-based algorithm (Suzuki-Kasami: N messages, or Raymond's tree: O(log N)).