DISTRIBUTED SYSTEM

DISTRIBUTED SYSTEM NOTES,IOE,TU,BCA

CLOCK SYNCHRONIZATION IN DISTRIBUTED SYSTEM

Clock synchronization in distributed systems is crucial to ensure that all nodes in the system operate with a consistent notion of time. This is important for coordinating actions, ordering events, and maintaining consistency across the system.

Algorithms such as Cristian's algorithm, Berkeley algorithm, and others are used to synchronize clocks across distributed nodes, compensating for clock drift and network delays.

CRISTIANS ALGORITHM

Cristian's Algorithm is a method used to synchronize the clocks of computers in a distributed system with a more accurate reference clock, typically provided by a time server. This algorithm is straightforward and useful for systems where high precision is not critical but where synchronization within a reasonable margin of error is necessary.

Cristian's Algorithm

1. Request Phase

• A client sends a request to the time server asking for the current time.

2. Response Phase

• The time server receives the request, records the time according to its own clock, and immediately sends back a response containing this recorded time.

3. Adjustment Phase

• The client receives the response and records the time at which the response was received.
• The client then calculates the round-trip delay and adjusts its clock based on the server's time and the estimated network delay.

Detailed Steps

1. Client Sends Request:

   • The client records the local time T0 when it sends a request to the time server.

2. Server Processes Request:

   • The server records the time Ts when it receives the request and then sends this time back to the client.

3. Client Receives Response:

   • The client records the local time T1​ when it receives the response from the server.

4. Calculate Round-Trip Delay:

   • The round-trip delay Δ estimated as Δ=T1−T0.

5. Adjust Client Clock:

   • The time at the server Ts is assumed to be the midpoint of the round-trip time. Therefore, the client adjusts its clock to Ts+(Δ/2).

Formula

Advantages

• Simplicity: The algorithm is easy to implement and requires minimal computational resources.
• Effectiveness: It provides reasonably accurate synchronization for many applications, especially in environments where precise timing is not critical.

BERKELEY ALGORITHM

Berkeley's Algorithm is a clock synchronization method used in distributed systems where there is no reliable external time source, such as a GPS or NTP server. Instead, it achieves synchronization by averaging the clock times of all participating nodes in the system.

How Berkeley's Algorithm Works

1. Coordinator Selection

• One node is chosen as the coordinator (also known as the master). This node is responsible for initiating and managing the synchronization process.

2. Time Collection

• The coordinator sends a request to all other nodes (slaves) asking for their current local time.

3. Time Reporting

• Each slave node responds with its local time to the coordinator.

4. Time Averaging

• The coordinator receives the times from all the slaves, including its own time. It calculates the average of these times.
• To account for message transmission delays, the coordinator may subtract the round-trip delay from the reported times of the slaves.

5. Clock Adjustment

• The coordinator sends the calculated average time (or the difference from the local time) back to each slave.
• Each slave node adjusts its clock based on the received time adjustment.

Formula

Advantages

• No External Time Source Needed: Berkeley's Algorithm is suitable for environments where an external time source like NTP or GPS is not available.
• Simplicity: The algorithm is straightforward to implement and understand.