DISTRIBUTED SYSTEM (IA-2) ANSWERS

1. Discuss the followings: (a) Clock Skew, (b) Clock Drift and
(c) Coordinated Universal Time.

OR from chatgpt
1. *Clock Skew*
 - *Definition*: The difference in time between clocks on different nodes in a
distributed system at a specific instant.
- *Cause*: Variations in initial synchronization or network delays during
synchronization.
- *Impact*: Inconsistencies in event ordering, leading to errors in time-sensitive
operations.
- *Mitigation*: Synchronization protocols like NTP (Network Time Protocol).

2. *Clock Drift*
- *Definition*: The gradual divergence of a clock's time from the actual time due
to imperfections in the clock's oscillator.
- *Cause*: Environmental factors (e.g., temperature) and hardware limitations.
- *Impact*: Over time, clocks on different nodes may desynchronize, requiring
correction.
- *Mitigation*: Frequent re-synchronization using reference clocks or protocols.

3. *Coordinated Universal Time (UTC)*

- *Definition*: The international standard time based on atomic clocks, used as a
reference for synchronization.
- *Role*: Ensures a common time base for all systems, reducing skew and drift
issues.
- *Implementation*: Distributed systems synchronize their local clocks to UTC
using protocols like NTP or PTP (Precision Time Protocol).

### Importance in Distributed Systems:

Accurate clock synchronization is essential to maintain event order, data
consistency, and system reliability.
2. Explain the Cristian’s method for synchronizing clocks
 Or from chartgpt
Cristian’s Method for Synchronizing Clocks:
Cristian's method is a simple and widely used algorithm for synchronizing the clocks of
nodes in a distributed system using a time server.

---

*Key Steps:*

1. *Request Time:*
- The client sends a request to the time server for the current time.

2. *Server Response:*
- The time server responds with its current time, \( T_s \).

3. *Round Trip Time (RTT):*

- The client measures the time it takes for the request and response to complete, \
( RTT \).
- RTT is calculated as:
\[
RTT = T_{recv} - T_{send}
\]
where \( T_{recv} \) is the time when the response is received, and \( T_{send} \) is the
time when the request was sent.

4. *Clock Adjustment:*
- The client assumes the network delay is symmetric, so the one-way delay is
approximated as:
\[
\text{Delay} = \frac{RTT}{2}
\]
- The client sets its clock to the adjusted time:
\[
T_{client} = T_s + \text{Delay}
\]

---

*Assumptions:*
- Network delay is symmetric (equal in both directions).
- The server's clock is accurate and synchronized to a reliable source.

---

*Limitations:*
- Asymmetry in network delays can lead to inaccuracies.
- Requires a trustworthy and synchronized time server.

---

*Use Case:*
Cristian's method is useful for environments where a centralized time server is available,
and precise synchronization is not critical.

3. What is a Logical Clock? Explain the Lamport’s logical clock.

OR from chatgpt
*3. Logical Clock*
- *Definition*: Logical clocks provide a way to order events in distributed systems without
relying on physical time.
- *Purpose: Ensures *causal ordering of events when physical clocks may not be
synchronized.

*Lamport’s Logical Clock*:

- *Key Idea*: Assigns a numerical timestamp to each event to establish their order.
- *Rules*:
1. *Increment Rule*: A process increments its logical clock (LC) before an event.
\[
LC = LC + 1
\]
2. *Send Rule*: A message carries the sender’s LC value.
3. *Receive Rule*: When a process receives a message, it updates its LC:
\[
LC = \max(LC_{\text{local}}, LC_{\text{message}}) + 1
\]
- *Result*: Events are ordered such that \( a \to b \implies LC(a) < LC(b) \), where \( a \to b \)
means \( a \) happens before \( b \)
4. Discuss the followings w.r.t Network Time Protocol: (a)
Design aims and features (b) Modes of NTP server
synchronization
 OR from chatgpt
Network Time Protocol (NTP)*

*(a) Design Aims and Features*:

- *Aims*:
1. Synchronize clocks of distributed systems to UTC.
2. Minimize clock drift and skew.
3. Achieve accuracy within milliseconds.

- *Features*:
1. *Hierarchical architecture*: Organized into stratum levels.
2. *Fault tolerance*: Multiple servers at each stratum ensure reliability.
3. *Adjustments*: Gradual corrections prevent abrupt clock changes.

*(b) Modes of NTP Server Synchronization*:

1. *Client-Server Mode*: Clients query servers to synchronize clocks.
2. *Symmetric Mode*: Peers exchange time information for mutual synchronization.
3. *Broadcast/Multicast Mode*: A server broadcasts time updates to multiple clients.

MODULE-4
5. Discuss the followings algorithms for mutual exclusion in
Distributed Systems: (a) central server algorithm (b) ring-
based algorithm (c) multicast and logical clocks.
( multicast and logical clocks. Is missing)

OR from chatgpt
*5. Mutual Exclusion Algorithms in Distributed Systems*

*(a) Central Server Algorithm*:

- *Mechanism*: A central server manages access to the critical section.
- *Steps*:
1. Process sends a request to the server.
2. Server grants access if the critical section is free; otherwise, queues the request.
3. Once access is released, the next process in the queue is granted access.
- *Advantages*: Simple and fair.
- *Disadvantages*: Single point of failure and bottleneck.

*(b) Ring-Based Algorithm*:

- *Mechanism*: Processes form a logical ring and pass a token.
- *Steps*:
1. The token circulates in the ring.
2. A process can enter the critical section only when holding the token.
- *Advantages*: No central coordinator.
- *Disadvantages*: Token loss requires recovery mechanisms.

*(c) Multicast and Logical Clocks*:

- *Mechanism*: Processes use Lamport's logical clocks and multicast messages.
- *Steps*:
1. A process sends a multicast request with its timestamp.
2. Other processes respond with acknowledgments.
3. A process enters the critical section only when it has the smallest timestamp and has
received acknowledgments from all others.
- *Advantages*: Ensures causal ordering.
- *Disadvantages*: High communication overhead
6. Explain the Maekawa’s voting algorithm for mutual
exclusion in Distributed Systems.
 OR from chatgpt
6. Maekawa’s Voting Algorithm*
- *Key Idea*: Each process only communicates with a subset of processes (its quorum).
- *Steps*:
1. A process requests permission to enter the critical section by sending messages to its
quorum.
2. Quorum members grant permission unless they’ve already granted it to another
process.
3. The process enters the critical section when all quorum members grant permission.
4. After exiting, the process releases locks by notifying quorum members.
- *Advantages*: Reduces communication overhead compared to full broadcast.
- *Disadvantages*: Deadlocks may occur if quorums overlap incorrectly.

MODULE-5
7. Discuss the various methods of concurrency control in
distributed transactions.

OR from chatgpt
7. Concurrency Control Methods in Distributed Transactions*
1. *Two-Phase Locking (2PL)*:
- Ensures serializability by acquiring locks in the first phase and releasing them in the
second.

2. *Timestamp Ordering*:
- Assigns timestamps to transactions to enforce ordering rules.

3. *Optimistic Concurrency Control*:

- Transactions execute without locks and validate at commit time.

4. *Distributed Deadlock Detection*:

- Tracks dependencies between transactions to detect and resolve deadlocks.

5. *Multiversion Concurrency Control (MVCC)*:

- Maintains multiple versions of data to allow concurrent reads and writes
8. Discuss (a) Phantom deadlocks and (b) Edge chasing w.r.t
deadlock in Distributed Systems.

OR from chatgpt
Deadlocks in Distributed Systems*

*(a) Phantom Deadlocks*:

- *Definition*: False detection of deadlocks due to delays or inconsistencies in the global
state.
- *Cause*: Message delays or outdated information during deadlock detection.
- *Mitigation*: Use up-to-date information and efficient deadlock detection algorithms.

*(b) Edge Chasing*:

- *Definition*: A distributed deadlock detection method.
- *Mechanism*:
 1. A process involved in a potential deadlock sends a probe message (edge) along its
dependency graph.
2. If the probe returns to the initiating process, a deadlock is detected.
- *Advantages*: Effective in detecting cycles in distributed wait-for graphs.
- *Disadvantages*: High communication overhead in large systems.