MutualExclusion

Question 1

What is mutual exclusion in distributed systems?

Answer 1

A condition where only one process can access a shared resource or perform a specific function at any given time.

Question 2

What is a critical section?

Answer 2

A section of code where a process accesses a shared resource. Only one process can be in the critical section at a time.

Question 3

What are some examples of mutual exclusion in real-world systems?

Answer 3

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.

Question 4

What are the key requirements for a mutual exclusion algorithm?

Answer 4

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.

Question 5

What is the centralized mutual exclusion algorithm?

Answer 5

A single coordinator manages access to the resource. Processes request access from the coordinator, which grants or denies access based on a queue.

Question 6

What are the benefits of the centralized mutual exclusion algorithm?

Answer 6

Safe, live, fair, and low complexity (3 messages per request).

Question 7

What are the problems with the centralized mutual exclusion algorithm?

Answer 7

Not robust: The coordinator is a single point of failure and a bottleneck.

Question 8

What is the Token Ring algorithm?

Answer 8

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.

Question 9

What are the benefits of the Token Ring algorithm?

Answer 9

Safe (only one process at a time has the token), live, and suitable for distributed resources.

Question 10

What are the problems with the Token Ring algorithm?

Answer 10

Not fair, inefficient (token must always be transmitted), not robust (token loss requires regeneration), and not suitable for large-scale systems.

Question 11

What is Lamport’s Mutual Exclusion Algorithm?

Answer 11

A fully distributed algorithm where each process maintains a request queue (FIFO) and uses logical clocks to order requests.

Question 12

What are the benefits of Lamport’s Mutual Exclusion Algorithm?

Answer 12

Safe, live, and fair.

Question 13

What are the problems with Lamport’s Mutual Exclusion Algorithm?

Answer 13

High complexity (3*(N-1) messages) and not robust (if a process dies, the algorithm is blocked).

Question 14

What is the Ricart & Agrawala Algorithm?

Answer 14

A simplification of Lamport’s algorithm that combines REPLY and RELEASE messages to reduce message traffic.

Question 15

What are the benefits of the Ricart & Agrawala Algorithm?

Answer 15

Safe, live, fair, and more efficient than Lamport’s (2*(N-1) messages).

Question 16

What are the problems with the Ricart & Agrawala Algorithm?

Answer 16

Not robust (N points of failure).

Question 17

What is a decentralized mutual exclusion algorithm?

Answer 17

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.

Question 18

What are the benefits of decentralized mutual exclusion algorithms?

Answer 18

More robust due to replicated coordinators, and probabilistically performs well in terms of liveness and fairness.

Question 19

What are the problems with decentralized mutual exclusion algorithms?

Answer 19

High demand can lead to many requests, and fairness is not guaranteed.

Question 20

What is the Distributed Hash Table (DHT) system structure?

Answer 20

A decentralized system structure that maps replicated controllers and resources to different nodes using a hash function.

Question 21

How does the decentralized mutual exclusion algorithm work?

Answer 21

A process requests permission from all coordinators associated with a resource’s replicas. Access is granted if a majority of coordinators approve.

Question 22

What is the main advantage of decentralized mutual exclusion algorithms over centralized ones?

Answer 22

Decentralized algorithms are more robust as they do not rely on a single coordinator.

Question 23

What are combinatorial schemes in mutual exclusion?

Answer 23

Schemes that allocate multiple resources simultaneously, often used in complex systems like cellular telephony or traffic control.

Question 24

How can mutual exclusion be achieved in systems with strategic agents?

Answer 24

Through negotiation among agents, considering cooperation, competition, or strategic reasons for accessing resources.

Question 25

What is the main trade-off in decentralized mutual exclusion algorithms?

Answer 25

They are more robust but complex and often involve probabilistic factors, which can lead to inefficiencies or unfairness.