Distributed Systems - Detailed Notes
I. Basic Concepts
Tightly and Loosely Coupled Processors
Tightly coupled systems share memory and clock; ideal for parallel systems. Loosely
coupled systems are independent processors communicating via a network, typical in
distributed environments.
Uniform and Non-Uniform Memory Access
Uniform Memory Access (UMA) gives equal memory access time for all processors. Non-
Uniform Memory Access (NUMA) provides faster local memory access, improving
scalability.
Blocking vs Non-Blocking | Synchronous vs Asynchronous
Blocking halts the process until operation completes; Non-blocking allows continued
execution. Synchronous waits for response; Asynchronous continues without waiting.
What is RMI and RPC? (Differences)
RMI (Remote Method Invocation) is Java-based and supports objects. RPC (Remote
Procedure Call) is language-neutral and supports remote function calls. RMI is object-
oriented; RPC is procedural.
Lamport Ordering & Causal Precedence
Lamport timestamps maintain logical order using counters. Causal precedence ensures
event A that causes B is always ordered before B. Causal is stricter than Lamport.
Message Passing vs Shared Memory
Message passing involves explicit communication (send/receive). Shared memory involves
read/write access to common memory space. Message passing is preferred in distributed
systems.
II. Consistency and Global State
Numerical Problem (Known + Consistent State)
Focuses on capturing a consistent snapshot across distributed systems to reflect a valid
global state without missing or duplicate messages.
Bagrodia’s Algorithm
Captures consistent global state using message tagging and logical clocks. Helps in
debugging, recovery, and fault tolerance.
How Global and Local States Are Formed
Local state refers to individual process status; Global state is the collective state including
in-transit messages. Must be consistent for accurate analysis.
III. Mutual Exclusion and Deadlock
Maekawa’s Algorithm
Uses quorum-based voting to achieve mutual exclusion, reducing message complexity
compared to all-to-all communication.
Suzuki-Kasami Algorithm
A token-based algorithm where a unique token circulates to grant critical section access,
reducing overhead.
Lamport’s Mutual Exclusion Algorithm
Uses logical timestamps and message queues to order critical section requests without
requiring a token.
Knapp’s Classification
Classifies global snapshots into consistent and inconsistent based on causality and message
states.
Models in Deadlock
Includes prevention, avoidance, detection, and recovery models, adapted to distributed
environments using wait-for graphs and timeout strategies.
IV. Checkpointing and Fault Tolerance
Coordinated vs Uncoordinated Checkpointing
Coordinated ensures a consistent snapshot by synchronizing processes. Uncoordinated may
lead to the domino effect if checkpoints aren't aligned.
Log-Based Rollback Mechanism
Uses logs to undo or redo operations post-failure. Includes pessimistic (before action) and
optimistic (after action) approaches.
Juang-Venkatesan Algorithm
Enables asynchronous checkpointing using message logging and dependency tracking,
minimizing coordination.
Asynchronous Checkpoint
Processes checkpoint independently, requiring complex recovery to ensure global
consistency.
Consistent State in Checkpoint
A consistent checkpoint ensures all received messages have matching sends and no
messages are lost or orphaned.