MutualExclusion Flashcards
What is mutual exclusion in distributed systems?
A condition where only one process can access a shared resource or perform a specific function at any given time.
What is a critical section?
A section of code where a process accesses a shared resource. Only one process can be in the critical section at a time.
What are some examples of mutual exclusion in real-world systems?
1) Database updates in an enterprise system. 2) Actuator control in IoT systems. 3) Autonomous vehicles accessing a narrow bridge. 4) Robots recharging at a charging base.
What are the key requirements for a mutual exclusion algorithm?
1) Safety: No two processes can be in the critical section simultaneously. 2) Liveness: Every process should eventually enter the critical section. 3) Fairness: All processes should have a fair chance to enter the critical section. 4) Efficiency: Low complexity. 5) Robustness: Tolerates failures.
What is the centralized mutual exclusion algorithm?
A single coordinator manages access to the resource. Processes request access from the coordinator, which grants or denies access based on a queue.
What are the benefits of the centralized mutual exclusion algorithm?
Safe, live, fair, and low complexity (3 messages per request).
What are the problems with the centralized mutual exclusion algorithm?
Not robust: The coordinator is a single point of failure and a bottleneck.
What is the Token Ring algorithm?
A distributed mutual exclusion algorithm where processes are arranged in a logical ring, and a token circulates among them. The process holding the token can enter the critical section.
What are the benefits of the Token Ring algorithm?
Safe (only one process at a time has the token), live, and suitable for distributed resources.
What are the problems with the Token Ring algorithm?
Not fair, inefficient (token must always be transmitted), not robust (token loss requires regeneration), and not suitable for large-scale systems.
What is Lamport’s Mutual Exclusion Algorithm?
A fully distributed algorithm where each process maintains a request queue (FIFO) and uses logical clocks to order requests.
What are the benefits of Lamport’s Mutual Exclusion Algorithm?
Safe, live, and fair.
What are the problems with Lamport’s Mutual Exclusion Algorithm?
High complexity (3*(N-1) messages) and not robust (if a process dies, the algorithm is blocked).
What is the Ricart & Agrawala Algorithm?
A simplification of Lamport’s algorithm that combines REPLY and RELEASE messages to reduce message traffic.
What are the benefits of the Ricart & Agrawala Algorithm?
Safe, live, fair, and more efficient than Lamport’s (2*(N-1) messages).
What are the problems with the Ricart & Agrawala Algorithm?
Not robust (N points of failure).
What is a decentralized mutual exclusion algorithm?
An approach where controllers and resources are replicated across multiple nodes. Processes request access from multiple coordinators, and access is granted based on a majority vote.
What are the benefits of decentralized mutual exclusion algorithms?
More robust due to replicated coordinators, and probabilistically performs well in terms of liveness and fairness.
What are the problems with decentralized mutual exclusion algorithms?
High demand can lead to many requests, and fairness is not guaranteed.
What is the Distributed Hash Table (DHT) system structure?
A decentralized system structure that maps replicated controllers and resources to different nodes using a hash function.
How does the decentralized mutual exclusion algorithm work?
A process requests permission from all coordinators associated with a resource’s replicas. Access is granted if a majority of coordinators approve.
What is the main advantage of decentralized mutual exclusion algorithms over centralized ones?
Decentralized algorithms are more robust as they do not rely on a single coordinator.
What are combinatorial schemes in mutual exclusion?
Schemes that allocate multiple resources simultaneously, often used in complex systems like cellular telephony or traffic control.
How can mutual exclusion be achieved in systems with strategic agents?
Through negotiation among agents, considering cooperation, competition, or strategic reasons for accessing resources.
What is the main trade-off in decentralized mutual exclusion algorithms?
They are more robust but complex and often involve probabilistic factors, which can lead to inefficiencies or unfairness.
