Process Synchronization & Mutual Exclusion: Algorithms, Deadlocks, and Coordination

TAKEAWAYS

• Mutual exclusion ensures only one process accesses a shared resource at a time, but distributed systems face challenges like message delays and failures.
• Synchronization primitives (e.g., semaphores, barriers) coordinate processes but require careful design to avoid deadlocks or starvation.
• Distributed deadlocks occur when processes wait indefinitely for resources held by others, requiring detection and recovery mechanisms.
• Clock synchronization (e.g., NTP) is critical for ordering events and timestamps in distributed systems.
• Algorithms like Lamport’s Bakery and Ricart-Agrawala solve mutual exclusion without a central coordinator.
• Real-world systems (e.g., eSewa transactions, Daraz order queues) use these principles to handle concurrent requests safely.

1. Mutual Exclusion in Distributed Systems

Mutual exclusion guarantees that only one process can access a shared resource (e.g., a database, a printer, or a critical section) at any time. In centralized systems, locks or semaphores suffice, but distributed systems add complexity due to:

• Message delays: A process may not receive a "release" message immediately.
• Failures: Nodes or networks can crash, leaving locks held indefinitely.
• No shared memory: Processes must rely on message passing.

Challenges in Distributed Mutual Exclusion

Requirements for a Distributed Mutual Exclusion Algorithm

1. Safety: No two processes enter the critical section simultaneously.
2. Liveness: Every process that requests access must eventually enter the critical section.
3. Fairness: No process is indefinitely delayed.
4. Deadlock freedom: The algorithm must not deadlock under any condition.

2. Synchronization Primitives

Synchronization primitives help coordinate processes. In distributed systems, common primitives include:

(A) Semaphores

A semaphore is a counter that controls access to a resource. It can be:

• Binary (mutex): Only 0 (locked) or 1 (unlocked).
• Counting: Tracks the number of available resources.

Operations:

• wait() (or P()): Decrements the semaphore. If it goes negative, the process blocks.
• signal() (or V()): Increments the semaphore. If processes are waiting, one is unblocked.

Example: Binary Semaphore for Mutual Exclusion

sequenceDiagram
    participant P1
    participant P2
    participant Resource
    P1->>Resource: wait() (lock)
    P2->>Resource: wait() (blocks)
    Resource-->>P1: Critical Section
    P1-->>Resource: signal() (unlock)
    Resource-->>P2: Critical Section

Problem in Distributed Systems:

• If a process crashes while holding the semaphore, the resource may be locked indefinitely.
• Solution: Use timeouts or heartbeat mechanisms to detect failures.

(B) Barriers

A barrier ensures all processes reach a certain point before any proceed. Useful for:

• Parallel algorithms (e.g., matrix multiplication).
• Synchronizing workers in a pipeline.

Example: Barrier in Distributed Computing

sequenceDiagram
    participant P1
    participant P2
    participant P3
    participant Barrier
    P1->>Barrier: Arrive
    P2->>Barrier: Arrive
    P3->>Barrier: Arrive
    Barrier-->>P1: Barrier reached
    Barrier-->>P2: Barrier reached
    Barrier-->>P3: Barrier reached
    Note right of Barrier: All processes proceed
    P1-->>Barrier: Exit
    P2-->>Barrier: Exit
    P3-->>Barrier: Exit

Implementation Challenges:

• How to count processes without shared memory?
• What if a process fails before reaching the barrier?

3. Distributed Deadlocks

A deadlock occurs when a set of processes are blocked forever, each waiting for a resource held by another. In distributed systems, deadlocks can arise due to:

• Circular wait: Process A holds resource X and waits for Y held by B, while B holds Y and waits for X.
• Indefinite blocking: A process waits indefinitely for a message it will never receive.

Deadlock Detection Algorithms

1. Wait-For Graph (WFG):

   • Nodes = processes or resources.
   • Edges = "Process P waits for resource R held by Q".
   • If the WFG has a cycle, a deadlock exists.

   graph TD
     P1-->|"waits for R1"| R1
     R1-->|"held by P2"| P2
     P2-->|"waits for R2"| R2
     R2-->|"held by P1"| P1

   This graph has a cycle (P1 → R1 → P2 → R2 → P1), indicating a deadlock.

2. Timeout-Based Detection:

   • If a process does not receive a response within a timeout, assume a deadlock.

Deadlock Recovery Strategies

Example: Deadlock in eSewa Transactions

• Suppose User A holds a lock on their account balance while waiting for User B’s transaction confirmation.
• If User B’s transaction fails and never releases the lock, User A is stuck.
• Solution: eSewa uses timeouts and compensating transactions to roll back failed operations.

4. Clock Synchronization

Distributed systems need logical clocks to order events consistently. Without synchronized clocks:

• Processes may misorder events (e.g., "A happened before B" vs. "B happened before A").
• Algorithms like mutual exclusion fail because timestamps are unreliable.

(A) Logical Clocks

• Lamport’s Clock: Each process maintains a logical clock that increments for each event.

  • Rules:
    1. LC[i] = 0 initially.
    2. For any event e, LC[e] > LC[parent(e)].
    3. If two events are concurrent, their clocks can be equal.

• Vector Clocks: Extends Lamport’s clock to track causality across multiple processes.

(B) Physical Clock Synchronization

Physical clocks (e.g., NTP) ensure all nodes have roughly the same time. Used in:

• Distributed databases (e.g., NEPSE stock market systems).
• Security systems (e.g., Khalti fraud detection).

Network Time Protocol (NTP)

• Uses client-server model to synchronize clocks.
• Steps:
  1. Client sends a request to NTP server.
  2. Server responds with its time and the time it sent the request.
  3. Client calculates the round-trip time and adjusts its clock.

Why NTP?

• Used by Google’s global infrastructure to synchronize servers worldwide.
• Ncell’s network uses NTP to ensure call routing is time-ordered.

5. Mutual Exclusion Algorithms

Two classic algorithms for distributed mutual exclusion:

(A) Lamport’s Bakery Algorithm

• Uses numbers to assign priorities.
• Steps:
  1. A process P_i wants to enter the critical section:
     • Sets number[i] = max(all numbers) + 1.
     • Sends number[i] to all other processes.
  2. If another process P_j has number[j] < number[i], it waits.
  3. If number[j] == number[i], compare process IDs (i < j goes first).

sequenceDiagram
    participant P1
    participant P2
    participant P3
    P1->>P2: number[1] = 3
    P1->>P3: number[1] = 3
    P2->>P1: number[2] = 2
    P2->>P3: number[2] = 2
    P3->>P1: number[3] = 1
    P3->>P2: number[3] = 1
    Note over P1,P2,P3: P3 enters first (lowest number)
    P3-->>P1: CS Entry (number[3] < number[1,2])
    P1-->>P3: CS Exit
    P2-->>P1: CS Entry (number[2] < number[1])
    P2-->>P3: CS Exit

Advantages:

• No deadlocks or starvation.
• Works even if processes fail (if they eventually send their numbers).

Disadvantages:

• High message overhead (each process sends its number to all others).

(B) Ricart-Agrawala Algorithm

• Uses request and reply messages.
• Steps:
  1. Process P_i sends a request message to all other processes.
  2. If a process P_j is not in its critical section, it replies yes.
  3. If P_j is in its critical section, it replies no and waits until P_i finishes.
  4. P_i waits until it receives yes from all processes.

sequenceDiagram
    participant P1
    participant P2
    participant P3
    P1->>P2: request
    P1->>P3: request
    alt P2 not in CS
    P2-->>P1: yes
    else P2 in CS
    P2-->>P1: no
    Note over P2: Waits until P1 exits
    end
    alt P3 not in CS
    P3-->>P1: yes
    else P3 in CS
    P3-->>P1: no
    Note over P3: Waits until P1 exits
    end
    P1->>P2: enter CS
    P1->>P3: enter CS
    P1-->>P2: release
    P1-->>P3: release

Advantages:

• Lower message overhead than Bakery.
• Fairness is guaranteed.

Disadvantages:

• Still requires message passing between all processes.

6. In the Real World

Distributed synchronization and mutual exclusion are everywhere. Here’s how:

(1) eSewa: Transaction Locking

• Idea: When you transfer money from eSewa, your account is locked until the transaction completes.
• How it works:
  • eSewa uses distributed locks to prevent double-spending.
  • If two users try to withdraw simultaneously, only one proceeds (mutual exclusion).
  • Clock synchronization ensures transactions are ordered correctly.

(2) Daraz: Order Processing Queue

• Idea: When you order on Daraz, your request joins a queue to avoid conflicts.
• How it works:
  • Daraz uses barriers to synchronize inventory checks.
  • If two users request the same item, only one is processed (mutual exclusion).
  • Deadlock detection prevents inventory from being locked indefinitely.

(3) NEPSE: Stock Market Synchronization

• Idea: Stock trades must be processed in order to avoid chaos.
• How it works:
  • NEPSE uses logical clocks to order trades.
  • NTP ensures all servers have synchronized time.
  • Distributed locks prevent two traders from buying the same stock simultaneously.

Worked Example: Bank Loan Approval

• Suppose a bank (e.g., NMB) processes loan requests from multiple branches.
• Problem: Two branches may try to approve the same loan simultaneously.
• Solution:
  1. Each branch sends a request to a central server.
  2. The server uses Lamport’s Bakery to assign priorities.
  3. Only one branch proceeds, while others wait.
  4. Clock synchronization ensures the loan is approved in the correct order.

7. Exam Tip

This unit tests conceptual understanding and application. Focus on:

1. Definitions: Know mutual exclusion, deadlock, and synchronization primitives.
2. Algorithms: Draw and explain Lamport’s Bakery and Ricart-Agrawala.
3. Clock Synchronization: Compare Lamport’s logical clocks vs. NTP.
4. Real-world ties: Relate to eSewa, Daraz, or NEPSE in answers.
5. Diagrams: Always include sequence diagrams for algorithms and WFG for deadlocks.

Common Pitfalls:

• Forgetting to mention fairness or deadlock freedom in algorithms.
• Not explaining message overhead in distributed solutions.
• Confusing logical clocks with physical clocks (NTP).

Sample Answer Structure:

1. Define the concept (e.g., mutual exclusion).
2. Explain challenges in distributed systems.
3. Describe an algorithm (e.g., Bakery) with a sequence diagram.
4. Compare with another method (e.g., Ricart-Agrawala).
5. Relate to a real-world example (e.g., eSewa).