UNIT-II SYNCHRONIZATION
DR. AMOL DHUMANE
PROBLEM WITH CLOCK
There is no single global clock in a distributed system.
Every computer ( any computing device but we are mostly concerned about server
side ) has its own clock and their materials, physical properties, clock rates are
different.
Also depending on environment of the location ( physical condition ) where the
servers are placed, oscillations of the clocks may get impacted due to temperature
variation.
So no two clocks would ever be exactly the same in terms of measuring time.
There could be some milliseconds or even seconds of difference between two clocks.
NEED OF SYNCHRONIZATION
Distributed System is a collection of computers connected via a high-speed communication network.
In the distributed system, the hardware and software components communicate and coordinate their
actions by message passing.
Each node in distributed systems can share its resources with other nodes.
So, there is a need for proper allocation of resources to
preserve the state of resources and help coordinate
between the several processes.
To resolve such conflicts, synchronization is used
CLOCK SYNCHRONIZATION
Clock synchronization in distributed systems refers to the process of ensuring that all
clocks within a distributed network are synchronized to a consistent time reference
Why Clock Synchronization is Important?
Consistency and Coherence: It ensures time-stamps and time-based decisions made across different
nodes in distributed systems are consistent and coherent.
Event Ordering: In distributed systems, events may occur on different machines. Synchronizing clocks
helps to establish a global order of events, which is critical for debugging, logging, and consistency.
Data Integrity & conflict resolution: This helps in maintaining Data Integrity & conflict resolution in the
scenarios concurrent updates and writes.
Fault detection and recovery: Timestamps can identify the sequence of events leading to fault which
can help in debugging and recovery process.
TYPES OF CLOCKS
Physical Clocks: Refer to real-world time (e.g., Coordinated Universal Time or UTC).
Addressing Time Disparities: When it comes to distributed systems each node operates with its clock, which can
result in variations. The goal of physical clock synchronization is to minimize these disparities by aligning the clocks.
Using UTC as a Common Reference Point: The key to achieving this synchronization lies in adjusting the clocks to
adhere to an accepted standard known as Universal Coordinated Time (UTC). UTC offers a reference for all nodes.
Logical Clocks: Focus on event ordering rather than actual timestamps.
Event Order Over Absolute Time: In the realm of distributed systems logical clock synchronization focuses on
establishing the order of events than relying on absolute time. Its primary objective is to establish connections
between events.
Approach towards Understanding Behavior: Logical clocks serve as storytellers weaving together a narrative of
events. This narrative enhances comprehension and facilitates coordination within the distributed system.
Mutual Exclusion Synchronization: This approach relies on creating a system where different processes
take turns accessing shared resources.
TYPES OF CLOCK SYNCHRONIZATION
Centralized
It is the one in which a time server is used as a reference.
The single time-server propagates it’s time to the nodes, and all the nodes adjust the time accordingly.
It is dependent on a single time-server, so if that node fails, the whole system will lose synchronization.
Examples of centralized are-Berkeley the Algorithm, Passive Time Server, Active Time Server etc.
Distributed
It is the one in which there is no centralized time-server present. The nodes adjust their time by using their local
time and then, taking the average of the differences in time with other nodes.
Distributed algorithms overcome the issue of centralized algorithms like scalability and single point failure.
Examples of Distributed algorithms are – Global Averaging Algorithm, Localized Averaging Algorithm, NTP
(Network time protocol), etc.
PHYSICAL CLOCK SYNCHRONIZATION TECHNIQUES
Cristian's Algorithm: Berkeley Algorithm:
A client requests the current time from a time server. A coordinator node polls all nodes for their current
clock times.
The server responds with its time.
Computes the average clock time (discarding outliers).
The client adjusts its clock considering network
latency. Adjusts all nodes’ clocks towards the computed
average.
Physical clock synchronization technique Physical clock synchronization technique
Network Time Protocol (NTP): Logical Clocks:
A widely used protocol for synchronizing clocks Lamport Timestamps: Ensure a partial ordering of
over the internet. events.
Uses a hierarchical structure of time servers to Vector Clocks: Provide a more detailed event
distribute accurate time. ordering by tracking the state of each process.
Physical clock synchronization technique
Mutual exclusion synchronization technique
CLOCK SYNCHRONIZATION - CRISTIAN'S ALGORITHM
It is used to synchronize time with a time
server by client processes.
This algorithm works well with low-latency
networks where Round Trip Time is short as
compared to accuracy.
Here Round Trip Time refers to the time
duration between the start of a Request and
the end of the corresponding Response.
• Major problem if time from time server is less than the client – resulting in time running backwards on the client!
(Which cannot happen – time does not go backwards).
• Minor problem results from the delay introduced by the network request/response: latency.
ALGORITHM
1) The process on the client machine sends the request for fetching clock time(time at the server) to the
Clock Server at time T_0 .
2) The Clock Server listens to the request made by the client process and returns the response in form of
clock server time.
3) The client process fetches the response from the Clock Server at time T_1 and calculates the
synchronized client clock time using the formula given below.
T_CLIENT = T_SERVER + (T_1 - T_0)/2
where T_CLIENT refers to the synchronized clock time,
T_SERVER refers to the clock time returned by the server,
T_0 refers to the time at which request was sent by the client process,
T_1 refers to the time at which response was received by the client process
The time at the client-side differs from actual time by at most (T1-T0)/2 seconds.
Conclusion: the error in synchronization can be at most (T1-T0)/2 seconds.
BERKELEY’S ALGORITHM
Berkeley’s Algorithm is a clock
synchronization technique used
in distributed systems.
The algorithm assumes that
each machine node in the
network either doesn’t have an
accurate time source or doesn’t
possess a UTC server.
OTHER CLOCK SYNCHRONIZATION ALGORITHMS
Both Cristian’s and the Berkeley Algorithm are centralized algorithms.
Decentralized algorithms also exist, and the Internet’s Network Time Protocol
(NTP) is the best known and most widely implemented.
NTP can synchronize clocks to within a 1-50 msec accuracy.
NETWORK TIME PROTOCOL (NTP)
The Network Time Protocol (NTP) is a networking protocol for clock
synchronization between computer systems over packet-switched, variable-
latency data networks.
In operation since before 1985, NTP is one of the oldest Internet protocols in
current use.
NTP was designed by David L. Mills of the University of Delaware.
Watch the video for details:
[Link]
LOGICAL CLOCKS
Synchronization based on “relative time”.
Note that (with this mechanism) there is no requirement for “relative time” to have any relation
to the “real time”.
What’s important is that the processes in the Distributed System agree on the ordering in
which certain events occur.
Such “clocks” are referred to as Logical Clocks.
PHYSICAL VS LOGICAL CLOCKS
A physical clock is a device that indicates what time it is.
A distributed system can have many physical clocks, and in general they will not agree.
A logical clock is the result of a distributed algorithm so that all parties can agree on the order
of events.
Examples of physical clocks are a clock on your wall, a watch, a computer time of day clock
and so forth.
An example of a logical clock is a Lamport Clock.
LOGICAL CLOCK SYNCHRONIZATION TECHNIQUES
Logical Clocks:
Lamport Timestamps: Ensure ordering of events.
Vector Clocks: Provide a more detailed event
ordering by tracking the state of each process.
Mutual exclusion synchronization technique
LAMPORT’S LOGICAL CLOCK
First point: if two processes do not interact, then their clocks do not need to be synchronized –
they can operate concurrently without fear of interfering with each other.
Second (critical) point:
It does not matter that two processes share a common notion of what the “real” current time is.
What does matter is that the processes have some agreement on the order in which certain events
occur.
Lamport used these two observations to define the “happens-before” relation (also often
referred to within the context of Lamport’s Timestamps).
THE “HAPPENS-BEFORE” RELATION (1)
If A and B are events in the same process, and A occurs before B, then we can
state that:
A “happens-before” B is true.
Equally, if A is the event of a message being sent by one process, and B is the event of the
same message being received by another process, then A “happens-before” B is also true.
(Note that a message cannot be received before it is sent, since it takes a finite, nonzero
amount of time to arrive … and, of course, time is not allowed to run backwards).
THE “HAPPENS-BEFORE” RELATION (2)
Obviously, if A “happens-before” B and B “happens-before” C, then it follows
that A “happens-before” C.
It therefore follows that if C(A) is the time on A, then C(A) < C(B), and so on.
THE “HAPPENS-BEFORE” RELATION (3)
Now, assume three processes are in a DS: A, B and C.
All have their own physical clocks.
A sends a message to B and includes a “timestamp”.
If this sending timestamp is less than the time of arrival at B, things are OK, as the “happens-before”
relation still holds (i.e., A “happens-before” B is true).
However, if the timestamp is more than the time of arrival at B, things are NOT OK.
THE “HAPPENS-BEFORE” RELATION (4)
How can some event that “happens-before” some other event possibly have occurred at a
later time??
The answer is: it can’t!
Lamport’s solution:
We need to have the receiving process adjust its clock forward to one more
than the sending timestamp value.
This allows the “happens-before” relation to hold, and also keeps all the
clocks running in a synchronized state.
The clocks are all kept in sync relative to each other.
LAMPORT’S LOGICAL CLOCKS (1)
The "happens-before" relation → can be observed directly in two situations:
If a and b are events in the same process,
and a occurs before b, then a → b is true.
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
Each process increments its clock counter between every two consecutive events.
If a sends a message to b, then the message must include T(a).
Upon receiving a and T(a), the receiving process must set its clock to max(T(a), Current Clock)+d.
That is, if the recipient’s clock is behind, it must be advanced to preserve the happen-before
relationship. Usually d=1.
LAMPORT’S LOGICAL CLOCKS (4)
Updating counter Ci for process Pi :
Before executing an event Pi executes
Ci ← Ci + 1.
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.
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.
By considering Local & External
events