Maekawa's algorithm
Encyclopedia
Maekawa's algorithm is an algorithm for mutual exclusion
on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.
Receiving site:
Critical section:
Quorum set (
):
A quorum set must abide by the following properties:
Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code in which a process or thread accesses a common resource...
on a distributed system. The basis of this algorithm is a quorum like approach where any one site needs only to seek permissions from a subset of other sites.
Terminology
- A site is any computing device which is running the Maekawa's Algorithm
- For any one request of the critical section:
- The requesting site is the site which is requesting entry into the critical section.
- The receiving site is every other site which is receiving the request from the requesting site.
- ts refers to the local time stamp of the system according to its logical clockLogical clockA logical clock is a mechanism for capturing chronological and causal relationships in a distributed system.Logical clock algorithms of note are:* Lamport timestamps, which are monotonically increasing software counters....
.
Algorithm
Requesting site:- A requesting site
sends a message 
to all sites in its quorum set 
.
Receiving site:
- Upon reception of a
message, the receiving site 
will:
- If site
does not have an outstanding 
message (that is, a 
message that has not been released), then site 
sends a 
message to site 
. - If site
has an outstanding 
message with a process with higher priority than the request, then site 
sends a 
message to site 
and site 
queues the request from site 
. - If sites
has an outstanding 
message with a process with lower priority than the request, then site 
sends an 
message to the process which has currently been granted access to the critical section by site 
. (That is, the site with the outstanding 
message.)
- If site
- Upon reception of a
message, the site 
will:
- Send a
message to site 
if and only if site 
has received a 
message from some other site or if 
has sent a yield to some other site but have not received a new 
.
- Send a
- Upon reception of a
message, site 
will:
- Send a
message to the request on the top of its own request queue. Note that the requests at the top are the highest priority. - Place
into its request queue.
- Send a
- Upon reception of a
message, site 
will:
- Delete
from its request queue. - Send a
message to the request on the top of its request queue.
- Delete
Critical section:
- Site
enters the critical section on receiving a 
message from all sites in 
. - Upon exiting the critical section,
sends a 
message to all sites in 
.
Quorum set (
):A quorum set must abide by the following properties:
-
-
-
- Site
is contained in exactly 
request sets
- Therefore:
-
Performance
- Number of network messages;
to 
- Synchronization delay: 2 message propagation delays
See also
- Lamport's bakery algorithmLamport's bakery algorithmLamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion....
- Lamport's Distributed Mutual Exclusion AlgorithmLamport's Distributed Mutual Exclusion AlgorithmLamport's Distributed Mutual Exclusion Algorithm is a contention-based algorithm for mutual exclusion on a distributed system.- Nodal properties :# Every process maintains a queue of pending requests for entering critical section order...
- Ricart-Agrawala algorithmRicart-Agrawala algorithmThe Ricart-Agrawala Algorithm is an algorithm for mutual exclusion on a distributed system. This algorithm is an extension and optimization of Lamport's Distributed Mutual Exclusion Algorithm, by removing the need for release messages...
- Raymond's algorithmRaymond's algorithmRaymond's Algorithm is a token based algorithm for mutual exclusion on a distributed system. It imposes a logical structure on distributed resources...