Mutual exclusion

Mutual exclusion is easy to handle if the entire request is atomic and needs to be coordinated if the request comprises multiple messages or spans multiple systems.

Mutual exclusion can be used to update a fields in database, modify a shared file or modify file contents that are replicated on multiple servers.

Distributed mutual exclusion

Goal: Create an algorithm to allow a process to request and obtain exclusive access to a resource that is available on the network.

Required properties:

1. Safety: at any instant only one process may hold the resource.
2. Liveness: the algorithm should make progress, processes should not wait forever for messages that will never arrive.
3. Fairness: each process gets a fair chance to hold the resource: bounded wait time & in-order processing of requests.
   • Process identification: every process has a unique ID (e.g., address, process id)

Assumptions (I have no idea where Шынназар got it from)

• Resource identification:
  • Assume there is agreement on how a resource is identified.
  • We’ll just use request(R) to request exclusive access to resource R
• Reliable communication: network messages are reliable (may require retransmission of lost/corrupted messages)
• Live processes: the processes in the system do not die

Categories of mutual exclusion

Permission-based

1. Centralized algorithm: a process can access a resource because a central coordinator allowed to do it
2. Distributed algorithm: a process can access a resource via a distributed agreement.

Token-based

A process can access a resource if it’s holding a token permitting it to do this.

- Centralized algorithm -