Distributed Systems Notes

Unit 1: Distributed Systems

1. Introduction to Distributed Systems

 Definition: A distributed system is a network of independent computers that

work together to provide a unified service or functionality, making it appear
like a single system to users.
 Key Features:
o Transparency: Hides complexities from the user (e.g., location of
resources, replication of data).
o Scalability: The system can grow by adding more nodes (computers)
without losing performance.
o Resource Sharing: Systems share hardware, software, or data across
nodes.
o Concurrency: Multiple processes or tasks can run simultaneously
across different machines.
o Fault Tolerance: Even if one part of the system fails, the rest of the
system continues to work smoothly.

2. Limitations of Distributed Systems

 Complexity: Designing and managing distributed systems is challenging

because of the need to coordinate multiple machines and handle various
issues.
 Security Risks: Distributed systems are more vulnerable to attacks,
requiring strict security mechanisms.
 Synchronization: Keeping data consistent across different nodes can be
difficult, especially when multiple nodes are updated simultaneously.
 Network Dependency: The performance of distributed systems depends on
the network's reliability and speed, meaning network failures can affect the
entire system's functionality.

3. Remote Procedure Call (RPC)

 Definition: RPC allows a program to execute a function on a remote system

as if it were local, abstracting network communication details.
 Steps:
1. Client calls a local procedure via the client stub (proxy).
2. Marshalling: The client stub packages the procedure arguments and
sends them over the network.
 3. Server stub: The server stub receives the request and unpacks the
arguments.
4. The server executes the procedure and sends the results back to the
client.
5. The client stub unpacks the results and returns them to the client
application.
 Diagram:
Client -> Stub -> RPC Runtime -> Network -> RPC Runtime -> Server Stub -
> Server

4. Remote Object Invocation (ROI)

 Definition: ROI extends RPC by allowing method calls on remote objects

(objects in other machines).
 Steps:
1. Client calls a method on a local stub representing a remote object.
2. The stub sends the method call and parameters over the network to
the server skeleton.
3. The skeleton invokes the method on the remote object.
4. The remote object executes the method and sends the result back to
the skeleton.
5. The skeleton returns the result to the client through the stub.
 Technologies: Java RMI (Remote Method Invocation), CORBA.
 Example: Java RMI, often used in enterprise applications.

5. Message-Oriented Communication

 Definition: Communication between distributed systems where components

exchange messages (data packets) instead of direct function calls.
 Types:
o Synchronous Communication: The sender waits for a reply after
sending a message (e.g., HTTP).
o Asynchronous Communication: The sender continues execution
without waiting for a response (e.g., email).
 Advantages:
o Decoupling: Sender and receiver do not need to be active
simultaneously.
o Scalability: Can handle many senders and receivers.

6. Unicasting, Multicasting, and Broadcasting

  Unicasting: One-to-one communication where a message is sent from a
single sender to a single receiver.
o Example: HTTP requests.
o Benefits: Private, reliable communication.
 Multicasting: One-to-many communication where data is sent from one
sender to a group of receivers.
o Example: Live video streaming to a specific group.
o Benefits: Efficient, reduces bandwidth.
 Broadcasting: One-to-all communication where data is sent to all devices on
a network.
o Example: ARP (Address Resolution Protocol).
o Benefits: Simple to implement for network-wide communication.

7. Group Communication

 Definition: Communication among multiple nodes or processes that need to

work together in a coordinated manner.
 Types:
o One-to-Many (Multicasting): One sender sends messages to
multiple receivers.
o Many-to-Many: Multiple senders send messages to multiple receivers
(e.g., collaborative applications).
o Many-to-One: Multiple senders send messages to one receiver (e.g.,
collecting data).
 Challenges:
o Reliability: Ensuring messages reach all members of the group.
o Consistency: Keeping the group’s state synchronized.
o Fault Tolerance: Handling node or network failures without
interrupting communication.
 Protocols:
o Reliable Multicast Protocols: Ensures messages are delivered
reliably to multiple receivers (e.g., IP Multicast).
o Atomic Broadcast: Ensures message order consistency (e.g., Paxos,
Raft).
o Membership Protocols: Tracks group members and their states
(e.g., Gossip Protocols).
 Example Use Cases:
o Distributed Databases: Synchronizing copies of data across multiple
locations.
o Collaborative Applications: Real-time editing tools (e.g., Google
Docs).
Unit 2: Distributed Operating Systems
1. Issues in Distributed Operating Systems

Distributed operating systems manage a collection of independent computers that

appear to users as a single system. Several challenges arise in this domain:

 Transparency:
Seamless access to resources without users being aware of the underlying
distribution.
o Access Transparency: Users can access resources without knowing
their location.
o Location Transparency: Resources can be moved without changing
their names.
o Replication Transparency: The system hides the fact that multiple
copies of a resource exist.
o Concurrency Transparency: Multiple users can access shared
resources simultaneously without conflict.
o Failure Transparency: The system masks failures and provides fault
recovery mechanisms.
 Fault Tolerance:
The ability to continue functioning in the presence of failures.
o Redundancy: Duplicates of critical components are maintained.
o Recovery Mechanisms: Processes restart after failure without user
intervention.
 Concurrency:
Managing multiple processes that execute simultaneously in a distributed
system.
o Efficient synchronization and resource sharing are critical.

2. Threads in Distributed Systems

Threads are lightweight processes within a distributed environment, allowing

efficient parallelism.

 Definition: Threads are independent units of execution within a single

process.
 Advantages:
o Faster context switching compared to processes.
o Lower memory overhead.
o Simplified communication between threads.
 Example:
A multi-threaded web server handles multiple client requests simultaneously
using separate threads for each client.
3. Clock Synchronization

In distributed systems, ensuring a consistent notion of time is critical because nodes

have independent clocks.

 Purpose:
To synchronize clocks across all nodes to maintain consistency in distributed
operations.
 Clock Synchronization Algorithms:
o Cristian’s Algorithm:
 A central time server provides the correct time to all nodes.
 The requesting node adjusts its clock based on the server's time
and network delay.
o Berkeley Algorithm:
 All nodes send their clock times to a coordinator.
 The coordinator computes the average time and adjusts the
clocks of all nodes to synchronize them.

4. Causal Ordering

Causal ordering ensures that events are processed in the order of their causal
relationships.

 Definition:
An event occurs before another if there is a causal dependency between
them.
 Example:
In a chat application, a reply should not appear before the original message it
responds to.
 Implementation:
Logical clocks (e.g., Lamport Timestamps) are often used to track causal
dependencies.

5. Global States

A global state is a snapshot of the distributed system at a specific point in time.

 Definition:
A snapshot capturing the state of all active processes and resources in the
system.
 Uses:
o Debugging: Identifying issues by analyzing the state.
o Checkpointing: Saving the system state for future recovery.
 o Fault Recovery: Restoring the system to a consistent state after a
failure.

6. Election Algorithms

Election algorithms are used to designate a leader in a distributed system to

coordinate activities.

 Purpose:
To elect a single node as a leader among distributed nodes.
 Examples:
o Bully Algorithm:
Nodes with higher priority (IDs) take over leadership if the current
leader fails.
o Ring Algorithm:
Nodes are arranged in a logical ring, and messages are passed to elect
the leader based on priority.

7. Distributed Mutual Exclusion

Mutual exclusion ensures that only one process can access a shared resource at a
time in a distributed environment.

 Definition:
A mechanism to prevent simultaneous access to shared resources.
 Algorithms:
o Token-Based:
A unique token is passed between nodes, granting access to the
resource.
o Timestamp-Based:
Processes send timestamped requests, and access is granted based on
the oldest request.

8. Distributed Deadlock

Deadlocks occur when processes block each other, waiting for resources.

 Definition:
A state in which two or more processes are unable to proceed because each
is waiting for the other to release resources.
 Solutions:
 o Timeouts:
Abort processes that wait for a resource beyond a specified timeout.
o Resource Allocation Graphs:
Use directed graphs to detect and resolve cycles, which indicate
deadlocks.

9. Agreement Protocols

Agreement protocols ensure that all nodes in a distributed system agree on a

common value or decision.

 Definition:
A mechanism to achieve consensus among distributed nodes.
 Example:
Byzantine Agreement Protocol:
o Designed to tolerate faults and malicious nodes.
o Ensures that non-faulty nodes agree on a single value, even if some
nodes fail or act maliciously.

Unit 3: Distributed Resource Management

[Link] Shared Memory (DSM)

DSM allows processes across distributed nodes to share a common memory space,
abstracting physical memory distribution.

Key Concepts:

1. Abstraction: Interact with a single memory space.

2. Types:
o Page-Based: Fixed-size pages shared across nodes.
o Object-Based: Flexible memory organization.
3. Consistency Models: Ensure data consistency across nodes.
4. Coherence: Maintain a consistent view of shared data.
5. Communication: Use RPCs or message passing for data access.

Advantages:

 Simplifies programming.
 Efficient resource management.
 Scales with new nodes.
Challenges:

 High latency.
 Complex consistency protocols.
 Synchronization issues.

2. Data-Centric Consistency Models

1. Definition: These models define how data updates are synchronized across
distributed nodes to maintain consistency.
2. Strong Consistency: All updates immediately visible to all clients.
3. Weak Consistency: Updates propagate eventually, allowing stale reads.
4. Eventual Consistency: All nodes converge to the same state over time.
5. Causal Consistency: Related operations are seen in the same order.
6. Read-Your-Writes Consistency: Writers see their changes immediately.

3. Client-Centric Consistency Models

1. Definition: These models focus on consistency from the perspective of

individual clients interacting with data.
2. Session Guarantees: Consistency within a client’s session.
3. Read-Your-Writes: Writers always see their changes.
4. Causal Consistency: Maintain order of causally related operations.

4. Distributed File Systems

 Definition: These systems manage files across multiple computers, making

them accessible as if stored locally.
 Examples:
o Google File System (GFS): Used for large-scale data storage with
high fault tolerance.
o Hadoop Distributed File System (HDFS): Designed for efficient
processing of large datasets, with built-in replication for reliability.
 Key Features:
o Scalability: Efficiently handles large data volumes.
o Fault Tolerance: Replicates data across nodes for reliability.
o High Performance: Optimized for read-heavy workloads.

5. Sun Network File System (NFS)

  Definition: NFS allows file access across a network as if the files are on the
local machine.
 How it works: It uses Remote Procedure Calls (RPCs) for accessing remote
files.
 Features:
o Stateless Design: The server doesn’t maintain client states,
simplifying implementation.
o Caching: Reduces network load by caching frequently accessed data
locally.
o Portability: Works across different operating systems and platforms.
 Use Case: Common in enterprise environments for file sharing and
collaboration.

Unit 4: Distributed Transaction Processing

1. Transactions

 Definition: A transaction is a sequence of operations performed as a single

logical unit of work, ensuring ACID properties (Atomicity, Consistency,
Isolation, Durability).
 Example:
o Banking system: Transferring money from one account to another
involves debiting one account and crediting another. Both operations
must succeed or fail together.

2. Nested Transactions

 Definition: Transactions divided into sub-transactions, allowing partial

rollback and more granular control.
 Example: A travel booking system where booking a flight, reserving a hotel,
and renting a car are sub-transactions of the main transaction.

3. Locks

 Definition: Mechanisms used to synchronize access to shared resources in a

distributed system.
 Example:
o A database record locked for updating by one transaction prevents
other transactions from accessing it until the lock is released.

4. Optimistic Concurrency Control

 Definition: A method where transactions execute without restrictions and

validate at commit to ensure no conflicts.
 Example:
 o A shopping cart system where changes are validated at checkout to
confirm stock availability.

5. Timestamp Ordering

 Definition: Transactions are ordered based on timestamps to ensure

serializability.
 Example:
o Assigning a unique timestamp to each transaction ensures older
transactions complete before newer ones.

6. Comparison of Concurrency Control Techniques

 Definition: Comparing different ways of handling transactions, like locks and

optimistic control, to see which works best.
 Example:
o Locking: Effective in high-contention scenarios.
o Timestamp Ordering: Ensures fairness but adds overhead.
o Optimistic Control: Suitable for low-contention environments.

7. Flat and Nested Distributed Transactions

 Definition: Flat transactions are simple and have no sub-transactions, while

nested transactions have smaller tasks inside them.
 Flat Transactions: Single start-to-end transactions.
 Nested Transactions: Hierarchical transactions with sub-transactions.
 Example:
o Flat: Transferring money between accounts.
o Nested: Booking a complete travel package.

8. Atomic Commit Protocols

 Definition: Protocols ensuring all participants in a transaction either commit

or abort.
 Examples:
o Two-Phase Commit (2PC): Prepare and commit phases.
o Three-Phase Commit (3PC): Adds a pre-commit phase for better
fault tolerance.

9. Concurrency Control in Distributed Transactions

 Definition: Concurrency control makes sure that multiple transactions can

happen without interfering with each other.
 Example:
o Using locks to prevent simultaneous updates to a shared resource.
o Timestamps to enforce execution order.

10. Distributed Deadlocks

  Definition: A deadlock happens when transactions are waiting on each other
and can’t finish.
 Example:
o Two transactions waiting for each other's resources.
o Resolution: Timeout mechanisms or cycle detection in wait-for
graphs.

11. Transaction Recovery

 Definition: Transaction recovery is the process of fixing things when

something goes wrong, like a system crash.
 Example:
o A system crash during a database update rolls back incomplete
changes using undo logging.

12. Overview of Replication

 Replication: Making copies of data and storing them in different places, so

the data is always available even if one place fails.
 Example:
o A distributed database replicating data across multiple servers to
ensure high availability.

13. Distributed Multimedia Systems

 Distributed Multimedia Systems: Systems that store and manage videos,

music, and other media across different locations.
 Example:
o Video streaming services like Netflix distribute multimedia content to
ensure smooth playback.

Unit 5: Fault Tolerance and Consensus

1. Fault Tolerance

Definition: Fault tolerance means a system can still work even if something goes
wrong with some of its parts.
Example: If one server in a website crashes, others take over, and the website
keeps running.

2. Distributed Commit Protocols

Definition: These are rules that help multiple computers in a system agree on
whether to finish or cancel a task.
Example: In a money transfer, both the sending and receiving banks must agree to
complete the transfer.
3. Byzantine Fault Tolerance (BFT)

Definition: BFT ensures the system works even if some parts act badly or give
wrong information.
Example: In a group of computers, if one computer lies, the others can still figure
out the right answer.

4. Impossibilities in Fault Tolerance

Definition: Sometimes, it’s impossible to make a system work perfectly in every

situation, especially when something fails.
Example: If a computer stops working in a voting system, it’s impossible to
guarantee that everyone will agree on the decision.