Centralized Algorithm: Mutual Exclusion in Distributed Systems

04 Apr 2011 by

Centralized Algorithm in Mutex

Centralized Algorithm in Mutex

Semaphore and Monitor that protected critical section in single system are no longer appropriated in distributed systems. So in distributed systems, we must use a special algorithm to achieve mutual exclusion. There are 3 basic algorithms to be considered and work as a baseline for developing another mutual exclusion algorithm in distributed systems. Those 3 are:

  • Centralized algorithm
  • Distributed algorithm
  • Token ring algorithm

Prerequisite

Please refer to these articles for better understanding of mutual exclusion:

Process

From the figure above, one node is elected as a coordinator. Coordinator is waiting for client request and issuing the token based on first come first serve. A token is an encrypted information that certify a particular node holding token to gain access to a shared resource. At a single time, only one node can hold the token. A node holding token will release token for other nodes whenever it does not need to access a shared resource anymore.

A cycle of token is (1) request token, (2) grant token, and (3) release token.

Advantages and Disadvantages

Advantages

  • First come first serve: it is fair and no process waits forever
  • It is easy to implement
  • It requires only 3 messages, request, grant, and release per use of a critical section

 

Disadvantages

  • If the coordinator crashes, the entire system may go down
  • Nodes cannot distinguish a dead coordinator from “permission denied”
  • A single coordinator may become a performance bottleneck
 

No responses yet

Leave a Reply