The Maekawa algorithm is a distributed mutual exclusion algorithm that allows processes to access shared resources in a mutually exclusive manner. It works by having a requesting process send a REQUEST message to all nodes in its site. It can enter the critical section if it receives a YES message from all nodes. Receiving nodes will vote YES unless they have already voted for another process, in which case they send an INQUIRE message to the candidate they voted for. The algorithm performs better than Lamport's and Ricart-Agrawala's algorithms with fewer messages and less synchronization delay but it is not fair.
The Maekawa algorithm is a distributed mutual exclusion algorithm that allows processes to access shared resources in a mutually exclusive manner. It works by having a requesting process send a REQUEST message to all nodes in its site. It can enter the critical section if it receives a YES message from all nodes. Receiving nodes will vote YES unless they have already voted for another process, in which case they send an INQUIRE message to the candidate they voted for. The algorithm performs better than Lamport's and Ricart-Agrawala's algorithms with fewer messages and less synchronization delay but it is not fair.
The Maekawa algorithm is a distributed mutual exclusion algorithm that allows processes to access shared resources in a mutually exclusive manner. It works by having a requesting process send a REQUEST message to all nodes in its site. It can enter the critical section if it receives a YES message from all nodes. Receiving nodes will vote YES unless they have already voted for another process, in which case they send an INQUIRE message to the candidate they voted for. The algorithm performs better than Lamport's and Ricart-Agrawala's algorithms with fewer messages and less synchronization delay but it is not fair.
The Maekawa algorithm is a distributed mutual exclusion algorithm that allows processes to access shared resources in a mutually exclusive manner. It works by having a requesting process send a REQUEST message to all nodes in its site. It can enter the critical section if it receives a YES message from all nodes. Receiving nodes will vote YES unless they have already voted for another process, in which case they send an INQUIRE message to the candidate they voted for. The algorithm performs better than Lamport's and Ricart-Agrawala's algorithms with fewer messages and less synchronization delay but it is not fair.
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
