Synchronization

Clock Synchronization

• When each machine has its own clock, an event that occurred
after another event may nevertheless be assigned an earlier time.
 Physical Clocks
• Computation of the mean solar day.
 Physical Clocks
• International Atomic Time (TAI) seconds are of constant length,
unlike solar seconds. Leap seconds are introduced when
necessary to keep in phase with the sun.
 Global Positioning System
• Computing a position in a two-dimensional space.
 Global Positioning System
• Real world facts that complicate GPS
1. It takes a while before data on a satellite’s position
reaches the receiver.
2. The receiver’s clock is generally not in synch with that of
a satellite.
 Clock Synchonization
• Let C(t) be a perfect clock
• A clock Ci(t) is called correct at time t if
Ci(t) = C(t)
• A clock Ci(t) is called accurate at time t if
dCi(t)/dt = dC(t)/dt = 1
• Two clocks Ci(t) and Ck(t) are synchronized at time t if Ci(t) =
Ck(t)
 Clock Synchronization Algorithms
• The relation between clock time and UTC when clocks tick at
different rates.
• Synchronization is required for
• Correctness
• Fairness
 Question
• Consider the behavior of two machines in a distributed system.
Both have clocks that are supposed to tick 1000 times per
millisecond. One of them actually does, but the other ticks only
990 times per millisecond. If UTC updates come in once a minute,
what is the maximum clock skew that will occur?
 Question & Answer

What is the difference between logical and physical clocks?

• Physical clocks measure the time of day.
• Logical clocks are used to mark relationships among events in a
distributed system.
 Processes and Events
• An Asynchronous Distributed System (DS) consists of a number of processes.
• Each process has a state (values of variables).
• Each process takes actions to change its state, which may be an instruction or
a communication action (send, receive).
• An event is the occurrence of an action.
• Each process has a local clock – events within a process can be assigned
timestamps, and thus ordered linearly.
• But – in a DS, we also need to know the time order of events across different
processes.
Clocks across processes are not synchronized in an asynchronous DS
 Network Time Protocol
• Getting the current time from a time server.
 Clock Synchronization in Wireless Networks

• The usual critical path in

determining network delays.
 Clock Synchronization in Wireless Networks

• The critical path in the case of

Reference broadcast
synchronization (RBS).
The Cristian’s Algorithm
 The Cristian’s Algorithm
• The process on the client machine sends the request for fetching
clock time(time at the server) to the Clock Server at time T0
• The Clock Server listens to the request made by the client process
and returns the response in form of clock server time.
• The client process fetches the response from the Clock Server at
time T1 and calculates the synchronized client clock time using
the formula
 The Berkeley Algorithm
• The time daemon asks all the other machines for their clock values.
• The time daemon tells everyone how to adjust their clock.
The Berkeley Algorithm
 The Berkeley Algorithm example

Machines Time before Synchonization Time after Synchonization

1 22/04/2024 13:10:24.180 22/04/2024 12:56:18.700
2 22/04/2024 12:55:15.030 22/04/2024 12:57:20.540
3 22/04/2024 13:00:24.080 22/04/2024 12:56:18.730
4 22/04/2024 12:50:15.130 22/04/2024 12:58:20.490
5 22/04/2024 13:00:24.230 22/04/2024 12:56:18.700
6 22/04/2024 12:55:15.180 22/04/2024 12:57:20.510
7 22/04/2024 13:00:23.930 22/04/2024 12:56:18.760
8 22/04/2024 12:50:15.280 22/04/2024 12:58:20.490
 Lamport’s Logical Clocks

• The "happens-before" relation → can be observed

directly in two situations:
1. If a and b are events in the same process, and a occurs
before b, then a → b is true.
2. If a is the event of a message being sent by one process,
and b is the event of the message being received by
another process, then a → b
 Lamport’s Logical Clocks

• Three processes, each with its own clock.

The clocks run at different rates.
 Lamport’s Logical Clocks

• Lamport’s algorithm corrects the clocks.

 Lamport’s Logical Clocks
• The positioning of Lamport’s logical clocks in distributed systems.
 Lamport’s Logical Clocks
• Updating counter Ci for process Pi
1. Before executing an event Pi executes Ci ← Ci + 1.
2. When process Pi sends a message m to Pj, it sets m’s timestamp
ts(m) equal to Ci after having executed the previous step.
3. Upon the receipt of a message m, process Pj adjusts its own
local counter as Cj ← max{Cj , ts (m)}, after which it then
executes the first step and delivers the message to the
application.
 Example: Totally Ordered Multicasting
• Updating a replicated database and leaving it in an inconsistent
state.
 Vector Clocks
• Concurrent message transmission
using logical clocks.
 Vector Clocks

• Vector clocks are constructed by letting each process Pi maintain

a vector VCi with the following two properties:
1. VCi [ i ] is the number of events that have occurred so far at Pi. In
other words, VCi [ i ] is the local logical clock at process Pi .
2. If VCi [ j ] = k then Pi knows that k events have occurred at Pj. It is
thus Pi’s knowledge of the local time at Pj .
 Vector Clocks
• Steps carried out to accomplish property 2 of previous slide:
1. Before executing an event Pi executes VCi [ i ] ← VCi [i ] + 1.
2. When process Pi sends a message m to Pj, it sets m’s (vector)
timestamp ts (m) equal to VCi after having executed the previous
step.
3. Upon the receipt of a message m, process Pj adjusts its own
vector by setting VCj [k ] ← max{VCj [k ], ts (m)[k ]} for each k, after
which it executes the first step and delivers the message to the
application.
 Enforcing Causal Communication
• Enforcing causal communication.
 Mutual Exclusion A Centralized Algorithm

• Process 1 asks the coordinator for

permission to access a hared resource.
Permission is granted.
 Mutual Exclusion A Centralized Algorithm

• Process 2 then asks permission to

access the same resource. The
coordinator does not reply.
 Mutual Exclusion A Centralized Algorithm

• When process 1 releases the resource,

it tells the coordinator, which then
replies to 2.
 A Distributed Algorithm
• Three different cases:
1. If the receiver is not accessing the resource and does not
want to access it, it sends back an OK message to the
sender.
2. If the receiver already has access to the resource, it simply
does not reply. Instead, it queues the request.
3. If the receiver wants to access the resource as well but has
not yet done so, it compares the timestamp of the incoming
message with the one contained in the message that it has
sent everyone. The lowest one wins.
 A Distributed Algorithm
• Two processes want to access a shared
resource at the same moment.
 A Distributed Algorithm
• Process 0 has the lowest timestamp, so it
wins.
 A Distributed Algorithm
• When process 0 is done, it sends an OK
also, so 2 can now go ahead.
 A Token Ring Algorithm
(a) An unordered group of processes on a network.
(b) A logical ring constructed in software.
 A Comparison of the Four Algorithms

• A comparison of three mutual exclusion algorithms.

 Global Positioning Of Nodes
• Computing a node’s position in
a two-dimensional space.
 Global Positioning Of Nodes
• Inconsistent distance measurements in a one-dimensional
space.
 Election Algorithms
• The Bully Algorithm
1. P sends an ELECTION message to all processes with
higher numbers.
2. If no one responds, P wins the election and becomes
coordinator.
3. If one of the higher-ups answers, it takes over. P’s job is
done.
 The Bully Algorithm
The bully election algorithm.
(a) Process 4 holds an election.
(b) Processes 5 and 6 respond, telling 4 to stop.
(c) Now 5 and 6 each hold an election.
 The Bully Algorithm
(d) Process 6 tells 5 to stop.
(e) Process 6 wins and tells everyone.
 A Ring Algorithm
• Election algorithm using a ring.
 Elections in Wireless Environments
• Election algorithm in a wireless network, with node a as the source.
(a) Initial network.
(b)–(e) The build-tree phase
 Elections in Wireless Environments
• Election algorithm in a wireless network, with node a as the source.
(b)–(e) The build-tree phase
 Elections in Wireless Environments
(e) The build-tree phase.
(f) Reporting of best node to source.
 Elections in Large-Scale Systems
• Requirements for super-peer selection:
1. Normal nodes should have low-latency access to super-peers.
2. Super-peers should be evenly distributed across the overlay
network.
3. There should be a predefined portion of super-peers relative to
the total number of nodes in the overlay network.
4. Each super-peer should not need to serve more than a fixed
number of normal nodes.
 Elections in Large-Scale Systems
• Moving tokens in a two-dimensional space using repulsion forces.