In distributed systems, mutual exclusion ensures that multiple processes do not access a shared resource (critical section) simultaneously. Maekawa's algorithm is a decentralized, non-token-based solution that uses quorums to achieve mutual exclusion efficiently.

The Concept of Quorums

A quorum is a subset of processes in the system. Each process is associated with its own quorum, and the key property is that any two quorums must have at least one process in common. This intersection ensures that only one process can enter the critical section at a time.

For a system with processes S = {P1, P2, ..., PN}, each process Pi has a quorum Si satisfying:

1. Intersection Property: Any two quorums share at least one process (Si ∩ Sj ≠ ∅).
2. Self-Inclusion: Each process is in its own quorum (Pi ∈ Si).
3. Equal Size: All quorums have the same size K.
4. Equal Responsibility: Each process appears in the same number of quorums D.

A practical way to construct quorums is using a sqrt(N) x sqrt(N) grid. Each process's quorum consists of its row and column in the grid, giving a quorum size of K = 2 * sqrt(N) - 1.

The Algorithm

The algorithm operates through message passing:

1. Requesting: Process Pi sends REQUEST(i, ts) to all processes in its quorum Si, where ts is the request timestamp.

2. Granting: Process Pj receiving a request can send GRANT(j) back only if it hasn't granted permission to another process. Otherwise, it queues the request, prioritizing by timestamp.

3. Entering Critical Section: Process Pi enters the critical section after receiving GRANT from all processes in its quorum.

4. Releasing: After exiting, Pi sends RELEASE(i) to all processes in its quorum.

5. Processing Release: Upon receiving RELEASE(i), process Pj grants permission to the next queued request.

Illustrative Example

Consider a system with 9 processes arranged in a 3x3 grid:

P1  P2  P3
          P4  P5  P6
          P7  P8  P9
          

The quorums are:

• P5's quorum: {P2, P4, P5, P6, P8} (row 2 + column 2)
• P1's quorum: {P1, P2, P3, P4, P7} (row 1 + column 1)

Notice that P5 and P1 share processes P2 and P4 in their quorums.

Suppose P5 and P1 both want to enter the critical section:

1. P5 sends REQUEST to {P2, P4, P5, P6, P8}
2. P1 sends REQUEST to {P1, P2, P3, P4, P7}
3. P2 and P4 (the shared processes) can only grant to one of them based on timestamp priority
4. If P5 has an earlier timestamp, P2 and P4 grant to P5
5. P5 receives all 5 grants and enters the critical section
6. P1 must wait for P5 to release before P2 and P4 can grant to P1

Message Complexity

The algorithm requires 3K messages per critical section entry: K for REQUEST, K for GRANT, and K for RELEASE. With the grid-based construction where K = 2 * sqrt(N) - 1, the complexity is O(sqrt(N)). This is significantly better than Lamport's algorithm with O(N) complexity.

Deadlock

Deadlock can occur when processes form a circular wait, each waiting for grants from others. For example, P1 waits for P2, P2 waits for P3, and P3 waits for P1.

To prevent deadlock, the algorithm uses an INQUIRE mechanism. When a process that has granted permission receives a higher-priority request (earlier timestamp), it sends INQUIRE to the current holder. If that holder hasn't received all its grants yet, it sends RELINQUISH, giving up its request to break the cycle.

Conclusion

Maekawa's algorithm provides an efficient decentralized solution to mutual exclusion with O(sqrt(N)) message complexity. While susceptible to deadlock, this is addressable through priority-based mechanisms, making it practical for distributed applications.