About this previous year paper
SECTION A – Very Short Answer Type
(2 × 10 = 20 Marks)
a) Challenges in detecting termination of distributed computations
In distributed systems, there is no global clock or shared memory, making it difficult to determine whether all processes have completed execution and no messages are in transit.
b) Techniques for message ordering
Message ordering techniques include:
FIFO ordering Causal ordering Total ordering
These ensure consistent message delivery across distributed processes.
c) Resource deadlock vs communication deadlock
Resource deadlock occurs when processes wait for resources held by others.
Communication deadlock occurs when processes wait indefinitely for messages.
d) Significance of mutual exclusion
Mutual exclusion prevents simultaneous access to shared resources, ensuring data consistency and avoiding race conditions.
e) Byzantine faults
Byzantine faults occur when components behave arbitrarily or maliciously, sending incorrect or conflicting information to other nodes.
f) Classification of agreement problems
Agreement problems include: Consensus
Byzantine agreement Atomic broadcast
Interactive consistency They ensure processes agree on a common value.
g) Recovery strategies in distributed databases
Recovery strategies include: Logging
Checkpointing Rollback recovery
Replication-based recovery
h) Role of checkpoints
Checkpoints save the consistent state of a process, allowing recovery without restarting from the beginning after a failure.
i) System model for group communication
It defines how processes communicate as groups, including membership management, message delivery guarantees, and fault assumptions.
j) Consistency challenges in replication
Challenges include: Update conflicts
Network latency Synchronization overhead
Maintaining data correctness across replicas
SECTION B – Long Answer Type
(Attempt any three – 10 Marks each)
2(a) Lamport Logical Clocks and Vector Clocks
Lamport clocks assign timestamps to events to establish causal ordering using the “happened-before” relation.
However, they cannot detect concurrent events.
Vector clocks overcome this limitation by maintaining a vector of counters, allowing precise detection of causality and concurrency.
Example:
In distributed databases, vector clocks help detect conflicting updates.
2(b) Edge-Chasing Algorithms in Distributed Deadlock Detection
Edge-chasing algorithms detect deadlocks by circulating probe messages along wait-for graphs.
Contribution: Detects cycles in distributed systems
Works without centralized control Efficient in dynamic environments
Example: Chandy–Misra–Haas algorithm.
2(c) Consensus Problem in Distributed Systems
Consensus requires all non-faulty processes to: Agree on a single value
Ensure validity Guarantee termination
Algorithms like Paxos and Raft handle failures and message delays to reach agreement reliably.
2(d) Challenges in Achieving Fault Tolerance
Challenges include: Partial failures
Network partitions Byzantine behavior
Performance overhead
Solutions involve replication, checkpointing, redundancy, and fault detection mechanisms.
2(e) Distributed Deadlocks
Distributed deadlocks occur across multiple nodes and differ from traditional deadlocks due to:
Lack of global state Message delays
Detection strategies include: Centralized detection
Distributed detection Hierarchical detection
SECTION C – Descriptive Answer Type
3(a) Real-World Examples of Distributed Systems
Examples include: Cloud computing platforms
Distributed databases (Google Spanner) Content delivery networks (CDNs)
Online banking systems
Benefits: Improved performance
High availability Fault tolerance
Challenges: Synchronization
Security Scalability
3(b) Architectural Models of Distributed Systems
Models:
Client–Server Peer-to-Peer
Multi-tier architecture
Client–Server suits centralized control, while P2P suits scalability and fault tolerance.
4(a) Performance Metrics for Mutual Exclusion Algorithms
Key metrics include: Message complexity
Response time Throughput
Fairness Fault tolerance
These metrics evaluate efficiency and scalability.
4(b) Centralized vs Distributed Deadlock Detection
| Aspect | Centralized | Distributed |
|---|---|---|
| Control | Single coordinator | Multiple nodes |
| Overhead | Low | Higher |
| Fault tolerance | Low | High |
5(a) Byzantine Agreement Problem
Approaches include: Oral messages
Signed messages Practical Byzantine Fault Tolerance (PBFT)
Effective solutions require: Redundancy
Authentication Fault masking
5(b) Atomic Commit Protocol
Atomic commit ensures that all nodes either commit or abort a transaction.
Importance: Maintains consistency
Handles partial failures Protocols like Two-Phase Commit (2PC) are widely used.
6(a) Commit Protocols in Fault Tolerance
Types: Two-Phase Commit (2PC)
Three-Phase Commit (3PC)
| Protocol | Strength | Weakness |
|---|---|---|
| 2PC | Simple | Blocking |
| 3PC | Non-blocking | High overhead |
6(b) Voting Protocols
Voting protocols allow nodes to collectively decide outcomes.
Uses: Replicated databases
Fault-tolerant storage systems They increase reliability despite failures.
7(a) Concurrency Control Methods
Methods include: Lock-based
Timestamp-based Optimistic concurrency control
Each offers trade-offs between performance and consistency.
7(b) Flat vs Nested Distributed Transactions
Flat transactions are simple and easy to manage.
Nested transactions allow partial commits and better fault isolation.
Challenges: Complexity
Coordination overhead
Advantages: Higher concurrency
Improved recovery