Unit 2

Unit 2: Distributed Operating Systems - Complete Notes

---

1. Issues in Distributed Operating Systems

Definition and Overview:

• A Distributed Operating System (DOS) manages a collection of independent computers and makes them appear as a single system.

• It handles resource sharing, communication, and coordination among distributed nodes.

Key Issues:

1. Transparency:

   • Users should not be aware that the system is distributed.

   • Example: Accessing files on a remote server should feel like accessing local files.

2. Scalability:

   • The system should handle growth in users, nodes, and resources.

   • Example: Adding more servers to a cloud system without downtime.

3. Fault Tolerance:

   • The system should continue functioning even if some nodes fail.

   • Example: Google’s distributed file system (GFS) continues working even if some servers fail.

4. Consistency:

   • Data should remain consistent across all nodes.

   • Example: Updating a file on one server should reflect on all other servers.

5. Security:

   • Protecting data and resources from unauthorized access.

   • Example: Encrypting data transmitted between nodes in a distributed system.

---

Mind Map for Issues in Distributed Operating Systems:

Issues in Distributed Operating Systems  
├── Transparency  
│   └── Example: Remote file access  
├── Scalability  
│   └── Example: Adding servers to a cloud  
├── Fault Tolerance  
│   └── Example: Google’s GFS  
├── Consistency  
│   └── Example: File updates across servers  
└── Security  
    └── Example: Data encryption

---

2. Threads in Distributed Systems

Definition:

• A thread is the smallest unit of execution within a process.

• In distributed systems, threads enable concurrent execution of tasks across multiple nodes.

Role of Threads:

1. Concurrency:

   • Threads allow multiple tasks to run simultaneously.

   • Example: A web server handling multiple client requests using threads.

2. Resource Sharing:

   • Threads share memory and resources within a process.

   • Example: A distributed database using threads to process queries.

3. Efficiency:

   • Threads reduce the overhead of creating separate processes.

   • Example: A distributed application using threads for parallel processing.

Challenges:

1. Synchronization:

   • Threads must be synchronized to avoid conflicts.

   • Example: Two threads updating the same data simultaneously.

2. Deadlocks:

   • Threads may wait indefinitely for resources.

   • Example: Two threads waiting for each other to release locks.

---

Mind Map for Threads in Distributed Systems:

Threads in Distributed Systems  
├── Role  
│   ├── Concurrency (Example: Web server)  
│   ├── Resource Sharing (Example: Distributed database)  
│   └── Efficiency (Example: Parallel processing)  
└── Challenges  
    ├── Synchronization (Example: Data conflicts)  
    └── Deadlocks (Example: Resource waiting)

---

3. Clock Synchronization

Definition:

• Clock synchronization ensures that all nodes in a distributed system have a consistent notion of time.

Why It’s Important:

1. Event Ordering:

   • Helps determine the order of events across nodes.

   • Example: Logging events in a distributed database.

2. Coordination:

   • Ensures tasks are executed at the correct time.

   • Example: Scheduling jobs in a distributed system.

Techniques:

1. Physical Clock Synchronization:

   • Synchronizing hardware clocks using protocols like NTP (Network Time Protocol).

   • Example: Synchronizing clocks across servers in a data center.

2. Logical Clock Synchronization:

   • Using logical clocks (e.g., Lamport timestamps) to order events.

   • Example: Ordering messages in a distributed messaging system.

---

Mind Map for Clock Synchronization:

Clock Synchronization  
├── Importance  
│   ├── Event Ordering (Example: Logging events)  
│   └── Coordination (Example: Job scheduling)  
└── Techniques  
    ├── Physical Clock (Example: NTP)  
    └── Logical Clock (Example: Lamport timestamps)

---

4. Causal Ordering

Definition:

• Causal ordering ensures that events that are causally related are processed in the correct order.

Why It’s Important:

• Prevents anomalies in distributed systems.

• Example: In a messaging system, a reply should not be processed before the original message.

Techniques:

1. Lamport Timestamps:

   • Assigns logical timestamps to events to preserve causality.

   • Example: Ordering messages in a chat application.

2. Vector Clocks:

   • Tracks causal relationships between events.

   • Example: Detecting conflicts in distributed databases.

---

Mind Map for Causal Ordering:

Causal Ordering  
├── Importance  
│   └── Prevents anomalies (Example: Messaging systems)  
└── Techniques  
    ├── Lamport Timestamps (Example: Chat applications)  
    └── Vector Clocks (Example: Distributed databases)

---

5. Global States

Definition:

• A global state is a snapshot of the entire distributed system at a particular time.

Why It’s Important:

• Helps in debugging, monitoring, and recovery.

• Example: Detecting deadlocks or inconsistencies in a distributed system.

Techniques:

1. Snapshot Algorithm:

   • Captures the global state of the system.

   • Example: Chandy-Lamport algorithm for distributed snapshots.

2. Consistent Global States:

   • Ensures the captured state is consistent.

   • Example: Detecting inconsistencies in distributed transactions.

---

Mind Map for Global States:

Global States  
├── Importance  
│   └── Debugging and recovery (Example: Deadlock detection)  
└── Techniques  
    ├── Snapshot Algorithm (Example: Chandy-Lamport algorithm)  
    └── Consistent Global States (Example: Distributed transactions)

---

6. Election Algorithms

Definition:

• Election algorithms are used to select a coordinator or leader in a distributed system.

Why It’s Important:

• Ensures a single node is responsible for coordination.

• Example: Electing a leader in a distributed database for write operations.

Algorithms:

1. Bully Algorithm:

   • The node with the highest ID becomes the leader.

   • Example: Electing a leader in a distributed system.

2. Ring Algorithm:

   • Nodes are arranged in a ring, and the leader is elected by passing messages.

   • Example: Leader election in a token ring network.

---

Mind Map for Election Algorithms:

Election Algorithms  
├── Importance  
│   └── Leader election (Example: Distributed databases)  
└── Algorithms  
    ├── Bully Algorithm (Example: Highest ID node)  
    └── Ring Algorithm (Example: Token ring network)

---

7. Distributed Mutual Exclusion

Definition:

• Distributed mutual exclusion ensures that only one process can access a shared resource at a time.

Why It’s Important:

• Prevents conflicts and ensures data integrity.

• Example: Multiple processes accessing a shared file in a distributed system.

Algorithms:

1. Token-Based Algorithms:

   • A token is passed among nodes to grant access.

   • Example: Token ring algorithm.

2. Permission-Based Algorithms:

   • Nodes request permission from other nodes to access resources.

   • Example: Ricart-Agrawala algorithm.

---

Mind Map for Distributed Mutual Exclusion:

Distributed Mutual Exclusion  
├── Importance  
│   └── Prevents conflicts (Example: Shared file access)  
└── Algorithms  
    ├── Token-Based (Example: Token ring algorithm)  
    └── Permission-Based (Example: Ricart-Agrawala algorithm)

---

8. Distributed Deadlock

Definition:

• Distributed deadlock occurs when processes in a distributed system are waiting for resources held by each other.

Why It’s Important:

• Deadlocks can halt the entire system.

• Example: Two processes waiting for each other to release locks in a distributed database.

Detection and Prevention:

1. Detection Algorithms:

   • Detect deadlocks by analyzing wait-for graphs.

   • Example: Chandy-Misra-Haas algorithm.

2. Prevention Techniques:

   • Avoid deadlocks by resource allocation strategies.

   • Example: Timeout-based resource allocation.

---

Mind Map for Distributed Deadlock:

Distributed Deadlock  
├── Importance  
│   └── Prevents system halts (Example: Distributed databases)  
└── Techniques  
    ├── Detection (Example: Chandy-Misra-Haas algorithm)  
    └── Prevention (Example: Timeout-based allocation)

---

9. Agreement Protocols

Definition:

• Agreement protocols ensure that all nodes in a distributed system reach a consensus.

Why It’s Important:

• Ensures consistency and reliability.

• Example: Reaching consensus on a transaction in a distributed database.

Protocols:

1. Two-Phase Commit (2PC):

   • Coordinates distributed transactions.

   • Example: Committing transactions in a distributed database.

2. Paxos Algorithm:

   • Ensures consensus in asynchronous systems.

   • Example: Leader election in distributed systems.

---

Mind Map for Agreement Protocols:

Agreement Protocols  
├── Importance  
│   └── Ensures consensus (Example: Distributed transactions)  
└── Protocols  
    ├── Two-Phase Commit (Example: Distributed databases)  
    └── Paxos Algorithm (Example: Leader election)

---

Summary of Unit 2: Distributed Operating Systems

• Distributed operating systems handle resource sharing, communication, and coordination in distributed systems.

• Key issues include transparency, scalability, fault tolerance, consistency, and security.

• Threads enable concurrency and resource sharing but face synchronization and deadlock challenges.

• Clock synchronization, causal ordering, and global states ensure consistency and coordination.

• Election algorithms, mutual exclusion, deadlock handling, and agreement protocols are essential for system reliability.

---

Final Mind Map for Unit 2:

Unit 2: Distributed Operating Systems  
├── Issues  
│   ├── Transparency, Scalability, Fault Tolerance, Consistency, Security  
├── Threads  
│   ├── Concurrency, Resource Sharing, Efficiency  
│   └── Synchronization, Deadlocks  
├── Clock Synchronization  
│   ├── Physical Clocks (NTP), Logical Clocks (Lamport Timestamps)  
├── Causal Ordering  
│   ├── Lamport Timestamps, Vector Clocks  
├── Global States  
│   ├── Snapshot Algorithm (Chandy-Lamport)  
├── Election Algorithms  
│   ├── Bully Algorithm, Ring Algorithm  
├── Distributed Mutual Exclusion  
│   ├── Token-Based, Permission-Based  
├── Distributed Deadlock  
│   ├── Detection (Chandy-Misra-Haas), Prevention (Timeout-based)  
└── Agreement Protocols  
    ├── Two-Phase Commit, Paxos Algorithm

---