 Distributed Operating Systems : Architecture of distributed operating

systems, system architecture types

Architecture of Distributed Operating Systems

A Distributed Operating System (DOS) is designed to manage multiple interconnected computers

that work together as a single system. Unlike centralized systems, DOS ensures resource sharing,
fault tolerance, and scalability while maintaining transparency for users.

Types of System Architecture in Distributed OS

Distributed OS architectures are classified based on how components interact and manage
resources. The primary architectures are:

1. Layered Architecture

Definition:
A Layered Architecture organizes the system into hierarchical layers, where each layer has a specific
function and interacts only with adjacent layers.

Components:

 Presentation Layer: Handles user interaction (UI) and data presentation.

 Application Layer: Contains business logic and system-specific functionalities.

 Middleware Layer: Manages communication and data exchange between system

components.

 Data Access Layer: Handles storage and retrieval of data from databases or distributed
storage systems.

Advantages:
✅ Separation of Concerns: Makes debugging and modifications easier.
✅ Modularity: Each layer operates independently, improving maintainability.
✅ Scalability: Layers can be scaled independently.

Disadvantages:
❌ Performance Overhead: Increased data transfer between layers may slow down the system.
❌ Complexity: Managing interactions between layers requires careful design.

Example: Web applications, enterprise software systems.

2. Peer-to-Peer (P2P) Architecture

Definition:
In P2P Architecture, all nodes (computers) function as both clients and servers, allowing direct
resource sharing without a central authority.

Key Features:
  Decentralized Network: No single server controls the system.

 Self-Organization: Nodes dynamically adjust connections based on availability.

 Scalability: Easily supports a large number of nodes.

Advantages:
✅ Fault Tolerance: The system remains operational even if some nodes fail.
✅ Cost-Effective: No expensive central servers are required.
✅ Efficient Resource Utilization: Peers share computational power and storage.

Disadvantages:
❌ Security Risks: Lack of a central authority makes it harder to enforce security.
❌ Performance Variability: The system's efficiency depends on individual node capabilities.

Example: BitTorrent (file sharing), blockchain networks.

3. Data-Centric Architecture

Definition:
A Data-Centric Architecture focuses on managing, storing, and processing data efficiently. It treats
data as a critical asset and structures the system around its flow.

Key Features:

 Centralized Data Management: Ensures consistency and reliability.

 Data Integration: Merges data from various sources for unified access.

 Scalability & Performance: Optimized for large-scale data processing.

Advantages:
✅ Consistency: Maintains a single source of truth.
✅ Data Quality: Reduces redundancy and ensures accuracy.
✅ Integration: Allows seamless access to different data sources.

Disadvantages:
❌ Single Point of Failure: A central data repository may become a bottleneck.
❌ Scalability Challenges: Managing large data sets requires advanced infrastructure.

Example: Databases like MySQL, PostgreSQL, and enterprise data warehouses.

4. Service-Oriented Architecture (SOA)

Definition:
SOA is a design paradigm where system functionalities are broken into independent services that
communicate over a network using standardized protocols.

Key Features:

 Loose Coupling: Services interact with minimal dependencies.

 Reusability: Services can be used across multiple applications.

  Interoperability: Works with different platforms using APIs.

Advantages:
✅ Flexibility: Services can be modified without affecting the whole system.
✅ Reusability: Reduces duplication of functionalities.
✅ Scalability: Individual services can be scaled as needed.

Disadvantages:
❌ Complex Management: Requires proper governance and coordination.
❌ Performance Overhead: Communication between services adds latency.

Example: Web services, API-driven applications, enterprise systems.

5. Event-Based Architecture

Definition:
In Event-Driven Architecture (EDA), components communicate by producing and consuming events
that represent system state changes.

Key Features:

 Event Producers & Consumers: Different parts of the system generate and react to events.

 Asynchronous Communication: Components operate independently.

 Event Channels: Events are transmitted via message queues or event streams.

Advantages:
✅ Scalability: Easily handles large-scale event processing.
✅ Real-Time Processing: Enables instant system responses.
✅ Flexibility: Adapts to dynamic conditions and changes.

Disadvantages:
❌ Complex Debugging: Hard to trace event flows in distributed systems.
❌ Event Ordering Issues: Ensuring events are processed in the correct sequence is challenging.

Example: IoT applications, real-time analytics, fraud detection systems.

6. Microservices Architecture

Definition:
A Microservices Architecture decomposes an application into small, independent services, each
responsible for a specific functionality.

Key Features:

 Single Responsibility: Each microservice focuses on a specific task.

 Autonomy: Services operate independently and communicate via APIs.

 Decentralized Data Management: Each service manages its own data.

Advantages:
✅ Scalability: Services can be scaled separately.
✅ Resilience: Failure in one service does not crash the entire system.
✅ Deployment Flexibility: Enables continuous updates and improvements.

Disadvantages:
❌ Complexity: Managing multiple services requires advanced orchestration.
❌ Data Consistency Issues: Maintaining consistency across services is difficult.

Example: Netflix, Amazon, banking systems.

7. Client-Server Architecture

Definition:
In Client-Server Architecture, clients request resources, and servers provide them. The system is
structured around central servers managing data and operations.

Key Features:

 Separation of Concerns: Clients handle user interactions, servers manage resources.

 Centralized Management: Servers control access to shared resources.

 Request-Response Model: Clients send requests, servers respond with the required data.

Advantages:
✅ Centralized Control: Easier to maintain and update.
✅ Resource Optimization: Servers efficiently manage shared resources.
✅ Security Management: Centralized security policies enhance protection.

Disadvantages:
❌ Single Point of Failure: If the server crashes, clients lose access.
❌ Scalability Challenges: High demand may overwhelm servers.
❌ Network Dependency: Clients rely on continuous network connectivity.

Example: Web applications, email systems, database management systems.

Conclusion

The architecture of a Distributed Operating System depends on system requirements like scalability,
fault tolerance, performance, and security. While Client-Server and Layered Architectures offer
centralized control, P2P, Microservices, and Event-Driven Architectures provide better scalability
and flexibility. SOA and Data-Centric models enhance interoperability and data consistency, making
them useful for enterprise applications.

 issues in distributed operating systems

Issues in Distributed Operating Systems
A Distributed Operating System (DOS) manages multiple interconnected computers as a single
system. While it offers advantages such as resource sharing, scalability, and fault tolerance, it also
comes with several challenges. These issues arise due to the distributed nature of computation, lack
of a global clock, network dependencies, and fault tolerance concerns.

1. Scalability Challenges

As the number of users, processes, and nodes increases, the system must efficiently scale without
performance degradation.

Problems:

 Handling Increased Load: More users and processes lead to higher computational and
communication demands.

 Geographic Distribution: Ensuring seamless performance across geographically dispersed

nodes.

Solutions:

✅ Horizontal Scaling: Adding more nodes to distribute the workload.

✅ Vertical Scaling: Enhancing the processing power of existing nodes.
✅ Sharding: Dividing databases into smaller, manageable parts to improve efficiency.

2. Reliability and Fault Tolerance

Reliability ensures continuous operation despite hardware or software failures. A distributed system
should continue functioning even if some nodes fail.

Problems:

 Node Failures: A system should tolerate individual node failures without affecting overall
performance.

 Data Loss & Corruption: Data must be replicated to prevent loss.

Solutions:

✅ Redundancy: Using duplicate components (e.g., backup servers, redundant storage).

✅ Failover Mechanisms: Automatic switching to a standby system when a primary component fails.
✅ Data Replication: Storing multiple copies of data across different locations.

3. Availability

Availability refers to ensuring that services remain accessible at all times, even during failures.

Problems:

 Downtime due to node failures or maintenance.

 Network failures causing partitioning of the system.

Solutions:

✅ High-Availability Architectures: Deploying redundant nodes to take over in case of failure.

✅ Load Balancers: Distributing incoming requests among multiple servers.
✅ Geographic Redundancy: Deploying servers in different locations to minimize failure impact.

4. Consistency (Data Synchronization Challenges)

A major challenge in distributed systems is ensuring consistent data across multiple nodes. The CAP
theorem states that a system can only guarantee two out of three:

 Consistency: All nodes have the same data at the same time.

 Availability: Every request receives a response.

 Partition Tolerance: The system functions even when communication between nodes fails.

Problems:

 Conflicting updates: Multiple nodes updating the same data can lead to inconsistencies.

 Eventual vs. Strong Consistency: Some systems prioritize availability over strong consistency.

Solutions:

✅ Strong Consistency: Ensure updates are immediately reflected across all nodes.
✅ Eventual Consistency: Allow temporary inconsistencies but guarantee synchronization over time.
✅ Consensus Algorithms (Paxos, Raft): Ensure consistent updates across distributed systems.

5. Latency Issues

Latency refers to the time delay in processing requests due to network delays and processing
overhead.

Problems:

 Network Delays: Communication across large distances introduces lag.

 Processing Overhead: Each node needs time to process requests.

Solutions:

✅ Caching: Storing frequently accessed data closer to users.

✅ Data Compression: Reducing the amount of data transmitted over the network.
✅ Edge Computing: Processing data closer to the source rather than in a central data center.

6. Load Balancing

Efficient load balancing is required to ensure no single node is overloaded while others remain idle.

Problems:

 Uneven Load Distribution: Some servers might receive more requests than others.
  Dynamic Workloads: Workloads vary over time, requiring dynamic adjustment.

Solutions:

✅ Round Robin Algorithm: Distributes requests evenly across available servers.

✅ Least Connections Method: Assigns new requests to the server with the fewest active connections.
✅ Dynamic Load Balancing: Continuously monitors workload and redistributes tasks as needed.

7. Security Issues

Distributed systems introduce security risks due to multiple nodes and network-based
communication.

Problems:

 Unauthorized Access: Without strict authentication, attackers can gain unauthorized entry.

 Data Breaches: Data traveling over networks can be intercepted.

 Malicious Nodes: Some nodes may act maliciously, disrupting operations.

Solutions:

✅ Authentication & Authorization: Verify users' identities and restrict access to resources.
✅ Data Encryption: Protect data in transit (SSL/TLS) and at rest.
✅ Firewall & Intrusion Detection: Monitor and prevent unauthorized activities.

8. Architectural Design Issues

Distributed systems need well-defined architectures for efficient functioning.

Challenges:

 Choosing the Right Model: Client-Server, Peer-to-Peer (P2P), or Microservices?

 Communication Overhead: Complex systems may require high inter-process

communication.

Solutions:

✅ Choosing the Right Architecture:

 Client-Server: Centralized control.

 P2P: Decentralized, fault-tolerant but complex.

 Microservices: Scalable but introduces networking overhead.

✅ Optimizing Message Passing: Reduce excessive communication between nodes.

9. Communication Issues

Communication in distributed systems happens through network protocols and message-passing

mechanisms.
Problems:

 Network Failures: Can disrupt communication between nodes.

 Message Loss: Data packets might be lost due to congestion or errors.

 Synchronous vs. Asynchronous Communication: Managing dependencies between

components.

Solutions:

✅ Reliable Network Protocols: TCP/IP for error-checked communication.

✅ Message Acknowledgment Mechanisms: Ensure messages are received and processed.
✅ Retry Logic & Timeouts: Automatically reattempt failed requests.

10. Data Management Issues

Managing distributed databases is complex due to data consistency, replication, and transaction
management.

Problems:

 Data Partitioning: Splitting data across nodes increases complexity.

 Distributed Transactions: Ensuring all nodes agree on a transaction’s outcome.

Solutions:

✅ Master-Slave Replication: One node updates, and others copy the changes.
✅ Multi-Master Replication: All nodes can read and write, increasing flexibility.
✅ Two-Phase Commit (2PC): Ensures consistency across multiple nodes.

Conclusion

Distributed Operating Systems enhance resource sharing, fault tolerance, and scalability, but they
also introduce challenges like scalability, reliability, consistency, security, and communication
issues. Optimizing architectures, using efficient algorithms, and employing robust security
measures can help address these problems.

 inherent limitation of distribute systems

Inherent Limitations of Distributed Systems
A Distributed System consists of multiple computers (nodes) working together as a single
system. While it offers scalability, fault tolerance, and resource sharing, it also has inherent
limitations due to its distributed nature, lack of global state, and communication
dependencies. These limitations arise from network delays, synchronization issues, and failure
handling.

1. Lack of a Global Clock

Problem:
Unlike centralized systems, distributed systems do not have a single, universal clock. Each node
maintains its own local clock, which may drift over time, leading to synchronization issues.
Challenges:
 Timestamp Ordering Issues: Events occurring on different nodes may appear in the wrong
order.
 Difficulties in Coordination: Scheduling tasks and ensuring consistency become complex.
 Message Delays Impacting Timestamps: Even if nodes synchronize periodically, network
latency can cause inconsistencies.
Solution Approaches:
✅ Logical Clocks (Lamport Clocks): Maintain event order instead of absolute time.
✅ Vector Clocks: Track causality relationships between events.
✅ Network Time Protocol (NTP): Periodically synchronizes node clocks with a reference time.

2. No Shared Memory (Lack of Global State)

Problem:
Distributed systems do not have a single shared memory. Each node has its own local memory,
making global decision-making more complex.
Challenges:
 Data Inconsistency: Different nodes might have different versions of the same data.
 High Overhead for Synchronization: Maintaining a consistent global state requires extra
messaging.
 Difficulties in Implementing Mutual Exclusion: Unlike centralized systems, distributed
systems cannot use shared variables (e.g., semaphores) for synchronization.
Solution Approaches:
✅ Distributed Shared Memory (DSM): Simulates shared memory across multiple nodes.
✅ Message Passing Mechanisms: Ensure communication and coordination between processes.
✅ Eventual Consistency Models: Allow temporary inconsistencies but ensure they resolve over
time.

3. Network Dependency & Latency Issues

Problem:
Distributed systems heavily rely on network communication, which introduces delays, message
loss, and unpredictable performance variations.
Challenges:
 High Latency: Messages take time to travel between nodes, causing delays.
 Network Partitions: If some nodes become unreachable, consistency and availability are
affected (as per the CAP theorem).
 Message Loss & Duplication: Messages may be lost or received multiple times due to
network failures.
Solution Approaches:
✅ Reliable Communication Protocols (TCP/IP): Ensure data delivery with error correction.
✅ Caching & Load Balancing: Reduce network traffic by storing frequently accessed data closer
to users.
✅ Redundant Networking: Use multiple communication paths to reduce failures.

4. CAP Theorem Limitation

Problem:
The CAP theorem states that a distributed system can provide only two out of three guarantees
at the same time:
 Consistency (C): All nodes see the same data at the same time.
 Availability (A): The system continues operating, even if some nodes fail.
 Partition Tolerance (P): The system works despite network partitions (communication
failures).
Challenges:
 A system must sacrifice one property at any given time.
o CP Systems: Ensure consistency and partition tolerance, but may become
unavailable.
o AP Systems: Ensure availability and partition tolerance, but allow temporary
inconsistencies.
o CA Systems (Theoretical Only): Cannot handle network failures, making them
impractical.
Solution Approaches:
✅ Choose trade-offs based on system needs:
 Banking systems prioritize consistency (CP).
 Social media platforms prioritize availability (AP).
✅ Use Eventual Consistency: Ensures all nodes synchronize eventually while remaining
available.

5. Fault Tolerance is Hard to Achieve

Problem:
In distributed systems, failures can occur at any level (hardware, network, or software), and
ensuring fault tolerance requires additional mechanisms.
Challenges:
 Failure Detection is Difficult: A failed node might be temporarily slow rather than completely
down.
 Partial Failures: Some nodes might fail while others continue operating, leading to
inconsistent states.
 Complex Recovery Mechanisms: Rolling back transactions in case of failure is complicated.
Solution Approaches:
✅ Replication & Redundancy: Store multiple copies of critical data across different nodes.
✅ Failure Detection Algorithms: Monitor node health using heartbeats and timeouts.
✅ Checkpointing: Save system state periodically to enable quick recovery.

6. Security Challenges
Problem:
Since distributed systems operate over networks, they are more vulnerable to cyber-attacks,
unauthorized access, and data breaches compared to standalone systems.
Challenges:
 Data Eavesdropping: Messages traveling over a network can be intercepted.
 Unauthorized Access: Without strong authentication, malicious users can exploit system
vulnerabilities.
 Compromised Nodes: A single compromised node can affect the entire system.
Solution Approaches:
 ✅ End-to-End Encryption: Secure communication between nodes.
✅ Access Control Mechanisms: Restrict access based on user roles.
✅ Intrusion Detection Systems (IDS): Monitor suspicious activities in the network.

7. Resource Management Complexity

Problem:
Distributed systems must efficiently manage and allocate CPU, memory, disk, and network
bandwidth across multiple nodes.
Challenges:
 Dynamic Resource Allocation: Workloads vary over time, requiring dynamic distribution.
 Task Scheduling Across Nodes: Processes should be assigned to nodes efficiently to avoid
bottlenecks.
 Load Balancing Issues: Some nodes may become overloaded while others remain idle.
Solution Approaches:
✅ Dynamic Load Balancing Algorithms: Distribute tasks based on real-time system load.
✅ Resource Virtualization: Use virtual machines (VMs) or containers to allocate resources
dynamically.
✅ Decentralized Scheduling: Allow nodes to make independent scheduling decisions.

8. Complexity in Debugging & Monitoring

Problem:
Debugging a distributed system is significantly harder than debugging a single-machine system
because of multiple interacting components.
Challenges:
 Difficult to Reproduce Bugs: Errors may depend on network conditions, making them
unpredictable.
 Lack of Global Log: Each node maintains its own logs, making centralized debugging difficult.
 Concurrency Issues: Multiple processes accessing shared resources lead to race conditions.
Solution Approaches:
✅ Distributed Logging Systems: Use tools like ELK Stack (Elasticsearch, Logstash, Kibana) to
aggregate logs.
✅ Tracing Mechanisms: Implement distributed tracing (e.g., OpenTelemetry, Jaeger) to track
requests across nodes.
✅ Automated Monitoring Tools: Use Prometheus, Grafana for real-time system health
monitoring.

Conclusion
Distributed systems offer scalability, reliability, and resource sharing, but their inherent
limitations—such as lack of a global clock, network dependency, CAP theorem constraints,
security challenges, and debugging difficulties—make them complex to manage. Addressing
these challenges requires careful architectural decisions, robust fault tolerance mechanisms,
and efficient synchronization techniques.

 distributed mutual exclusion: classification of mutual exclusion algorithms

Distributed Mutual Exclusion: Classification of Mutual Exclusion Algorithms

What is Mutual Exclusion?

Mutual exclusion ensures that only one process at a time can access a shared resource or critical
section (CS) in a distributed system. Unlike centralized systems, distributed systems lack shared
memory and rely on message passing to achieve mutual exclusion.

Classification of Mutual Exclusion Algorithms

Mutual exclusion algorithms in distributed systems are broadly classified into two categories:

1. Token-Based Algorithms

2. Non-Token-Based (Permission-Based) Algorithms

Each category has its own strengths and weaknesses, depending on message complexity, fault
tolerance, and fairness.

1. Token-Based Algorithms

Concept:

 A unique token is circulated among processes.

 A process must possess the token to enter its critical section.

 Once finished, it passes the token to another process.

Advantages:

✅ No Starvation: Every process eventually gets the token.

✅ Low Message Complexity: Requires only 1 message per CS entry if the token is available.
✅ Fairness: Requests are served in a first-come, first-served (FIFO) manner.

Disadvantages:

❌ Token Loss Problem: If the token is lost, it must be regenerated.

❌ Single Point of Failure: If the process holding the token crashes, mutual exclusion breaks.

Examples of Token-Based Algorithms:

a) Suzuki-Kasami’s Broadcast Algorithm

 Each process maintains a sequence number for CS requests.

 A process requests the token by broadcasting its request.

 The token holder sends the token to the requesting process with the smallest sequence
number.

 Message Complexity: O(N) (since a broadcast is needed).

b) Ricart-Agrawala’s Token-Based Algorithm

 A logical timestamp is used to order requests.

 The token moves in a predefined logical ring order.

  If a process doesn’t need the token, it simply forwards it.

 Message Complexity: O(1) per CS execution (if token is available).

2. Non-Token-Based (Permission-Based) Algorithms

Concept:

 A process sends a request to all other processes.

 It must receive permission (REPLY messages) from all nodes before entering CS.

 Once done, it releases the CS and informs other processes.

Advantages:

✅ No Token Loss Problem: No need to regenerate a lost token.

✅ Fault Tolerance: If a requesting process crashes, the system remains functional.

Disadvantages:

❌ High Message Complexity: Requires O(N) messages per request.

❌ Starvation Possible: A process may never get enough replies due to network delays.

Examples of Non-Token-Based Algorithms:

a) Lamport’s Algorithm

 Each request is assigned a logical timestamp.

 Requests are stored in a queue and processed in timestamp order.

 A process enters the CS only after receiving replies from all other processes.

 Message Complexity: 3(N − 1) messages per CS execution.

o N-1 REQUEST messages

o N-1 REPLY messages

o N-1 RELEASE messages

b) Ricart-Agrawala’s Permission-Based Algorithm

 Uses only 2(N − 1) messages by eliminating some redundant replies.

 If a process receives a request while inside CS, it delays its reply.

 Message Complexity: 2(N − 1) messages per CS execution.

Comparison of Token-Based vs. Non-Token-Based Algorithms

Feature Token-Based Algorithms Non-Token-Based Algorithms

Message
Low (1–N messages) High (2N–3N messages)
Complexity

Fairness High (FIFO ordering) High (timestamp ordering)

No token loss, but requires recovery

Failure Handling Token loss is an issue
mechanisms

Starvation Rare (FIFO ensures fairness) Possible (if requests are delayed)

Systems with high request

Best Use Case Systems requiring strong fault tolerance
frequency

3. Hybrid Algorithms

Some distributed mutual exclusion algorithms combine token-based and permission-based

approaches to improve performance.

Example: Maekawa’s Quorum-Based Algorithm

 Instead of broadcasting requests to all nodes, a process only contacts a subset (quorum) of
nodes.

 Message Complexity: O(√N) instead of O(N) (better than pure permission-based

approaches).

 Trade-Off: Finding an optimal quorum set is challenging.

Conclusion

The choice of a mutual exclusion algorithm depends on network conditions, fault tolerance, and
performance requirements.

 Token-Based Algorithms are efficient but require token recovery mechanisms.

 Non-Token-Based Algorithms provide better failure handling but incur higher message
complexity.

 Hybrid Algorithms try to balance both approaches.

 Lamport’s, Suzuki-Kasami’s Broadcast algorithm,

Lamport’s Algorithm & Suzuki-Kasami’s Broadcast Algorithm
Mutual exclusion in distributed systems ensures that only one process enters the critical
section (CS) at a time. Since there is no shared memory in a distributed system, mutual
exclusion is achieved through message passing.
Here, we discuss two important algorithms for distributed mutual exclusion:
1. Lamport’s Algorithm (Permission-Based)
2. Suzuki-Kasami’s Broadcast Algorithm (Token-Based)
 1. Lamport’s Algorithm (Permission-Based)
Proposed by Leslie Lamport, this is a non-token-based algorithm that uses timestamps to
maintain fairness.
It ensures requests are executed in increasing order of their timestamps, guaranteeing FIFO
ordering.
Working Mechanism:
💡 Uses three message types:
 REQUEST (T, i) → Sent when a process wants to enter CS (T = timestamp, i = process ID).
 REPLY → Sent when a process grants permission to another process.
 RELEASE → Sent when a process exits the CS, allowing others to proceed.
Algorithm Steps:
Entering the Critical Section:
1️⃣ A process S_i that wants to enter the CS sends a REQUEST(T, i) message to all other
processes.
 The timestamp T is assigned using Lamport’s Logical Clock.
 The process adds its own request to a local queue ordered by timestamp.
2️⃣ When another process S_j receives the REQUEST message:
 If S_j is not in the CS, it immediately sends a REPLY to S_i.
 If S_j is in the CS or has a request with a smaller timestamp, it delays the reply.
3️⃣ S_i can enter the CS if:
 It has received a REPLY from all (N-1) processes.
 Its own request is at the top of its queue.
Exiting the Critical Section:
4️⃣ When S_i exits the CS, it:
 Removes its request from its queue.
 Sends a RELEASE message to all processes.
 Each receiving process removes S_i’s request from its queue.

Example of Lamport’s Algorithm Execution:

Consider three processes (P1, P2, P3):

Event Action

P1 wants CS Sends REQUEST (T1, 1) to P2, P3

P2 wants CS (later) Sends REQUEST (T2, 2) to P1, P3

P3 receives both requests P3 grants REPLY to P1 (T1 < T2)

P1 enters CS P1 got REPLY from both P2 and P3

P1 exits CS Sends RELEASE to P2, P3

P2 enters CS P2 now gets all needed replies

Message Complexity:
 3(N – 1) messages per CS execution
o N – 1 REQUEST messages
o N – 1 REPLY messages
 o N – 1 RELEASE messages
 Total: 3(N-1) messages per critical section execution.
Advantages of Lamport’s Algorithm:
✅ Fairness: Requests are executed in timestamp order (FIFO).
✅ No Token Loss: Works even if a process crashes.
✅ Simple & Logical: Uses only message passing.
Disadvantages of Lamport’s Algorithm:
❌ High Message Overhead: Requires 3(N-1) messages per CS execution.
❌ Delay in Execution: A process must wait for all replies, which may cause delays.
❌ No Fault Tolerance: If a process fails and does not send REPLY, others cannot proceed.

2. Suzuki-Kasami’s Broadcast Algorithm (Token-Based)

Proposed by Suzuki & Kasami, this is a token-based algorithm that allows mutual exclusion
by passing a unique token.
A process can enter the critical section only if it holds the token.
Working Mechanism:
💡 Uses:
 REQUEST(i, SN_i): Sent when a process requests the token.
 TOKEN: Grants permission to enter the critical section.
Algorithm Steps:
Entering the Critical Section:
1️⃣ A process S_i that wants to enter the CS:
 Increments its request sequence number (SN_i).
 Sends a REQUEST(i, SN_i) message to all (N-1) processes.
2️⃣ When a process S_j receives REQUEST(i, SN_i):
 Updates its RN[i] value as RN[i] = max(RN[i], SN_i).
 If it has the token and S_i’s request is next in line, it sends the TOKEN to S_i.
Executing the Critical Section:
3️⃣ S_i can enter CS only if it holds the TOKEN.
Exiting the Critical Section:
4️⃣ After exiting the CS, S_i:
 Updates the LN[i] value in the token (indicating the last executed request).
 Checks which process needs the token next (from RN values).
 Passes the token to the next eligible process.

Example of Suzuki-Kasami’s Algorithm Execution:

Consider three processes (P1, P2, P3) with token initially at P1:

Event Action

P2 requests CS Sends REQUEST(2, SN2) to P1, P3

P1 receives REQUEST Updates RN[2] = SN2

P1 exits CS Checks RN[], sends TOKEN to P2

P2 enters CS Holds the token, executes CS

P2 exits CS Updates LN[], checks RN[], sends TOKEN to next process

 Message Complexity:
 O(1) if the token is already at the requesting process.
 O(N) if the token must be passed.
Advantages of Suzuki-Kasami’s Algorithm:
✅ Low Message Complexity: Uses only 1 message per CS execution if the token is available.
✅ Fairness: Requests are served in FIFO order.
✅ Better Fault Tolerance: If a process crashes, the token can be regenerated.
Disadvantages of Suzuki-Kasami’s Algorithm:
❌ Token Loss Problem: If the token is lost, it must be regenerated (requires a separate
algorithm).
❌ Higher Memory Overhead: Each process must maintain an RN array (request sequence
numbers).
❌ Idle Token Problem: A process may hold the token without using it, delaying others.

Comparison of Lamport’s and Suzuki-Kasami’s Algorithm

Lamport’s Algorithm Suzuki-Kasami’s Algorithm

Feature
(Permission-Based) (Token-Based)

Message O(1) if token is available,

3(N-1) per CS
Complexity O(N) otherwise

Synchronization Uses timestamps Uses token

No fault tolerance (reply Handles failures but token

Fault Tolerance
delay blocks system) loss is a problem

Starvation Possible (delayed replies) Not possible (FIFO order)

Maintains strict order via FIFO token queue ensures

Fairness
timestamps fairness

Systems requiring strict High-performance

Best For
ordering distributed systems

Conclusion
Both Lamport’s and Suzuki-Kasami’s algorithms provide distributed mutual exclusion but
are suited for different use cases:
 Lamport’s Algorithm is better when fairness and timestamp-based ordering are required,
but it has high message complexity.
 Suzuki-Kasami’s Algorithm is more efficient in message passing but requires token
management.

 Distributed deadlock detection,

Distributed Deadlock Detection
What is a Deadlock in Distributed Systems?
 A deadlock occurs when a group of processes in a distributed system are waiting for
resources that are held by each other, forming a circular wait condition where no process
can proceed.
In distributed systems, deadlock detection is challenging due to:
1. Lack of global memory – No single system has complete knowledge of resource allocation.
2. No central coordinator – Processes execute independently across multiple nodes.
3. Communication Delays – Message passing introduces delays in detecting deadlocks.

Conditions for Deadlock (Coffman’s Conditions)

For a deadlock to occur, the following four conditions must hold simultaneously:
1️⃣ Mutual Exclusion – A resource is held by one process at a time.
2️⃣ Hold and Wait – A process holds resources while waiting for more.
3️⃣ No Preemption – A resource cannot be forcibly taken from a process.
4️⃣ Circular Wait – A set of processes form a cycle where each is waiting for a resource held
by the next process.

Types of Deadlocks in Distributed Systems

1. Resource Deadlock
Occurs when processes wait for resources (e.g., CPU, memory, files) held by others.
📌 Example:
 Process P1 holds R1 and waits for R2.
 Process P2 holds R2 and waits for R1 → Deadlock occurs.
2. Communication Deadlock
Occurs when processes wait indefinitely for messages from each other.
📌 Example:
 Process A waits for a message from Process B.
 Process B waits for a message from Process A.
 Neither can proceed → Deadlock occurs.
3. Livelock (Starvation)
A process keeps changing state in response to deadlock prevention mechanisms but never
progresses.
📌 Example:
 Two processes repeatedly try to request and release resources but never get access.

Deadlock Detection Techniques in Distributed Systems

Since distributed systems lack a centralized resource manager, deadlock detection must be
performed cooperatively by multiple nodes.
1. Centralized Deadlock Detection
A single node (central coordinator) monitors all resource requests and detects deadlocks.
🔹 Working:
 All processes send their resource requests to the coordinator.
 The coordinator maintains a Wait-For Graph (WFG) and checks for cycles.
 If a cycle is detected → Deadlock exists.
✅ Advantages:
 Simple to implement.
 Easy to track resource dependencies.
❌ Disadvantages:
 Single Point of Failure: If the coordinator fails, detection stops.
 Scalability Issues: Overhead increases with system size.

2. Distributed Deadlock Detection (Decentralized Approach)

Each process monitors its own resources and cooperates with others to detect deadlocks.
Key Approaches:
A. Wait-For Graphs (WFG)
Each process maintains a local WFG and periodically exchanges information with others.
🔹 Working:
 Each process checks its local WFG for cycles.
 Periodically, nodes exchange local WFGs to build a global WFG.
 If a cycle exists in the global WFG → Deadlock detected.
✅ Advantages:
 No single point of failure.
 Works well in large systems.
❌ Disadvantages:
 High message complexity due to frequent graph updates.
 Delayed detection in asynchronous systems.
B. Chandy-Misra-Haas Algorithm (Edge-Chasing Algorithm)
This distributed algorithm detects deadlocks by passing probes along the dependency
graph.
🔹 Working:
 If P1 waits for P2, it sends a probe message.
 The probe travels through all dependent processes.
 If the probe returns to P1, a cycle exists → Deadlock detected.
✅ Advantages:
 Efficient for detecting deadlocks incrementally.
 Low overhead compared to global WFG methods.
❌ Disadvantages:
 False deadlocks may occur due to delayed probe messages.
 Difficult to handle dynamic resource allocation.

3. Hybrid Deadlock Detection

Combines centralized and distributed techniques for better performance.
🔹 Working:
 Uses a centralized coordinator for logging resource requests.
 Distributed nodes detect cycles locally and report potential deadlocks.
 The central system verifies and resolves deadlocks.
✅ Advantages:
 Reduces communication overhead.
 More scalable than purely centralized methods.
❌ Disadvantages:
 Still has a partial dependency on a central coordinator.
 Complex to implement.

Deadlock Handling Strategies

Once a deadlock is detected, the system must resolve it using one of these techniques:
1. Deadlock Prevention
 Avoids deadlocks by ensuring at least one Coffman’s condition does not hold.
🔹 Techniques:
 Avoid Circular Wait: Impose an ordering on resource requests.
 No Hold and Wait: Force a process to request all resources at once.
✅ Advantage: No deadlocks occur.
❌ Disadvantage: Leads to poor resource utilization.

2. Deadlock Avoidance (Banker’s Algorithm)

A process only proceeds if the system remains in a safe state after resource allocation.
🔹 Working:
 Each process declares its maximum resource need.
 The system allocates resources only if they won’t lead to a deadlock.
✅ Advantage: Prevents deadlocks dynamically.
❌ Disadvantage: Requires prior knowledge of resource needs.

3. Deadlock Recovery
If a deadlock is detected, the system must recover by forcefully terminating or preempting
processes.
A. Process Termination
 Kill one or more processes involved in deadlock.
 Choose the process with the least impact.
✅ Advantage: Simple and effective.
❌ Disadvantage: Can lead to loss of work and data inconsistency.
B. Resource Preemption
 Forcibly take resources from a process and assign them to another.
 Rollback the preempted process and restart it later.
✅ Advantage: Preserves process execution.
❌ Disadvantage: High overhead due to process rollbacks.

Comparison of Deadlock Detection Techniques

Method Advantages Disadvantages

Centralized Detection Easy to implement Single point of failure

High communication
Distributed WFG No single failure point
overhead

Edge-Chasing (Chandy- Low overhead, good May generate false

Misra-Haas) scalability positives

Balances performance Complex

Hybrid Approach
and reliability implementation

Conclusion
🔹 Deadlocks in distributed systems are harder to detect and resolve than in centralized
systems.
🔹 Detection methods include centralized, distributed (WFG, edge-chasing), and hybrid
approaches.
 🔹 Deadlocks can be prevented, avoided (Banker’s Algorithm), or resolved via process
termination or resource preemption.

 Distributed file systems,

 Distributed shared memory,

 Distributed scheduling