Maekawa
Algorithm
Jyothis Jagan
182IT011
Introduction
DME Algorithms
Maekawa Algorithm
Meakawa’s
Algorithm
Requirements
Algorithm Jyothis Jagan
Comparison and
Performance 182IT011
Summary
References
April 9, 2019
Introduction
Maekawa
Algorithm
Jyothis Jagan
182IT011 Mutual Exclusion
Introduction Concurrent access of processes to a shared resource or
DME Algorithms data is executed in mutually exclusive manner.
Meakawa’s
Algorithm
Requirements
Algorithm
In a distributed system, semaphores cannot be used
Comparison and
Performance to implement mutual exclusion.
Summary
Message passing is the sole means for implementing
References
distributed mutual exclusion.
DME Algorithms
Maekawa
Algorithm
Jyothis Jagan
182IT011
Introduction
DME Algorithms
Meakawa’s Permission Based Algorithms
Algorithm
Requirements Meakawa’s DME Algorithm
Algorithm
Comparison and
Performance Token Based Algorithms
Summary
References
Meakawa’s DME Algorithm
Maekawa
Algorithm
Jyothis Jagan
182IT011
The system consists of N sites, S1 , S2 , S3 ... SN
Introduction
1 For any combination of i and j,
DME Algorithms
Meakawa’s
1 ≤ i, j ≤ N, Si ∩ Sj 6= φ
Algorithm
Requirements 2 Si , 1 ≤ i ≤ N, always contains i
Algorithm
Comparison and
Performance 3 The size of Si , | Si | , is K for any i. That is,
Summary | S1 | = | S2 | = | S3 | = ... = | Sn | = K
References
4 Any j, 1 ≤ j ≤ N, is contained in the D Si ’s,
1 ≤ i ≤ N.
Algorithm
Maekawa
Algorithm
Requesting Node
Jyothis Jagan
182IT011 1 A requesting node i sends message REQUEST(TS,i)
Introduction to all nodes in Si
DME Algorithms 2 It can execute Critical Section when it gets YES
Meakawa’s
Algorithm from all nodes in Si
Requirements
Algorithm Receiving Nodes
Comparison and
Performance
Upon reception of REQUEST(TS,i) message, the
Summary
References
node j will:
1 if j haven’t vote for a node, then it sends YES to i
2 if j have voted, then:
1 if TSvoted candidate < TSi , then add the request to
queue. Otherwise send INQUIRE to voted
candidate.
Algorithm(cont.)
Maekawa
Algorithm
Jyothis Jagan
182IT011
Upon reception of INQUIRE message at j from i
Introduction
DME Algorithms
1 send RELINQUISH message to i if j is not in its
Meakawa’s
critical section.
Algorithm
Requirements
Algorithm Upon reception of RELINQUISH message at j from i
Comparison and
Performance
1 Send YES to the node at tope of WaitingQueuej
Summary
References
Upon reception of RELEASE message at j from i
1 Send YES to the node at tope of WaitingQueuej
Comparison and Performance
Maekawa
Algorithm
Jyothis Jagan
182IT011
Introduction
√ √
Number of messages; 3 N to 5 N
DME Algorithms
Meakawa’s Synchronization delay: 2 messages
Algorithm
Requirements The algorithm is not fair
Algorithm
Comparison and
Performance Number of messages per CS invocations is lesser
Summary than Lamport’s DME Algorithm and
References
Ricart-Agrawala’s DME Algorithm
Summary
Maekawa
Algorithm
Jyothis Jagan
182IT011
Introduction
DME Algorithms Five types of messages - REQUEST, YES,
Meakawa’s
Algorithm
INQUIRE, RELINQUISH and RELEASE
Requirements
Algorithm
Performs better than Lamport’s DME Algorithm
Comparison and
Performance and Ricart-Agrawala’s DME Algorithm
Summary
not a fair algorithm
References
References
Maekawa
Algorithm
Jyothis Jagan
182IT011
Introduction
DME Algorithms Wikipedia , https://en.wikipedia.org
√
Meakawa’s Mamoru Maekawa. 1985. A N algorithm for mutual exclusion in decentralized systems. ACM
Algorithm
Trans. Comput. Syst. 3, 2 (May 1985), 145-159. DOI: https://doi.org/10.1145/214438.214445
Requirements
Algorithm Prof.Ananthanarayana V.S, NPTEL - Computer Science and Engineering - Distributed Computing
Comparison and
Performance Systems, https://nptel.ac.in/courses/106106107/
Summary Ajay Kshemkalyani and Mukesh Singhal, Distributed Computing: Principles, Algorithms, and
References Systems, Cambridge University Press, https://www.cs.uic.edu/ ajayk/Chapter9.pdf
