(SEM VII) THEORY EXAMINATION 2023-24 DISTRIBUTED COMPUTING SYSTEM

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

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)

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