UNIT III

SYNCHRONIZATION IN DISTRIBUTED
SYSTEMS
Clock synchronization -Physical Clocks, Logical Clocks.
Clock Synchronization Algorithms. Scalor time, Vector time.
Logical clocks - Lamport's Logical Clocks, Vector Clocks.
Physical
clock Synchronization- NTP.
In a centralized system, time is unambiguous. When a
process wants to know the time, it makes a system call
and the kernel tells it.

If process A asks for the time. and then a little later

process B asks for the time, the value that B gets will be
higher than (or possibly equal to) the value A got. It will
certainly not be lower.

In a distributed system, achieving agreement on time is

not trivial.

2
In distributed computing, where multiple systems
collaborate to accomplish tasks ensuring that all the
clocks are synchronized plays a crucial role.

Clock synchronization involves aligning the clocks of

computers or nodes, enabling efficient data transfer,
smooth communication, and coordinated task execution.

What is Clock Synchronization in Distributed

Systems?
Clock synchronization in distributed systems refers to the
process of ensuring that all clocks across various nodes
or computers in the system are set to the same time or
at least have their times closely aligned.
•In a distributed system, where multiple computers
communicate and collaborate over a network, each3
computer typically has its own local clock.
•However, due to factors such as hardware differences,
network delays, and clock drift (inaccuracies in
timekeeping), these local clocks can drift apart over
time.

Importance of Clock Synchronization

Below are the importance of clock synchronization in
distributed system:
•Consistency and Coherence:
• Clock synchronization ensures that timestamps and
time-based decisions made across different nodes in
the distributed system are consistent and coherent.
This is crucial for maintaining the correctness of
distributed algorithms and protocols. 4
•Event Ordering:
• Many distributed systems rely on the notion of event
ordering based on timestamps to ensure causality
and maintain logical consistency. Clock
synchronization helps in correctly ordering events
across distributed nodes.
•Data Integrity and Conflict Resolution:
• In distributed databases and file systems,
synchronized clocks help in timestamping data
operations accurately. This aids in conflict resolution
and maintaining data integrity, especially in
scenarios involving concurrent writes or updates.

5
•Fault Detection and Recovery:
• Synchronized clocks facilitate efficient fault
detection and recovery mechanisms in distributed
systems. Timestamps can help identify the
sequence of events leading to a fault, aiding in
debugging and recovery processes.
•Security and Authentication:
• Timestamps generated by synchronized clocks are
crucial for security protocols, such as in
cryptographic operations and digital signatures.
They provide a reliable basis for verifying the
authenticity and temporal validity of transactions
and messages.

6
 Physical Clocks
Nearly all computers have a circuit for keeping track of
time. Despite the widespread use of the word "clock" to
refer to these devices, they are not actually clocks in the
usual sense. Timer is perhaps a better word.

A computer timer is usually a precisely machined quartz

crystal. When kept under tension, quartz crystals
oscillate at a well-defined frequency that depends on the
kind of crystal, how it is cut, and the amount of tension.

Associated with each crystal are two registers, a counter

and a holding register. Each oscillation of the crystal
decrements the counter by one. When the counter gets
to zero, an interrupt is generated and the counter 7is
reloaded from the holding register. In this way, it is
possible to program a timer to generate an interrupt 60
With a single computer and a single clock, it does not
matter much if this clock is off by a small amount. Since
all processes on the machine use the same. clock, they
will still be internally consistent. For example, if the file
input.c has time 2151 and file input.o has time 2150, make
will recompile the source file, even if the clock is off by
2 and the true times are 2153 and 2152, respectively.
All that really matters are the relative times.

As soon as multiple CPUs are introduced, each with its

own clock, the situation changes radically. Although the
frequency at which a crystal oscillator runs is usually
fairly stable, it is impossible to guarantee that the
crystals in different computers all run at exactly the
8
same frequency.
In practice, when a system has n computers, all n
crystals will run at slightly different rates, causing the
(software) clocks gradually to get out of synch and give
different values when read out. This difference in time
values is called clock skew.

In some systems (e.g., real-time systems), the actual

clock time is important. Under these circumstances,
external physical clocks are needed. For reasons of
efficiency and redundancy, multiple physical clocks are
generally considered desirable, which yields two
problems: (1) How do we synchronize them with
realworld clocks. and (2) How do we synchronize the
clocks with each other?

9
CLOCK SYNCHRONIZATION ALGORITHMS
Centralized
Passive and active time server

Distributed
Global averaging distributed algorithm
Local averaging distributed algorithm
CLOCK SYNCHRONIZATION ALGORITHMS
Passive time server centralized algorithm

Each node sends message to time server

Time server replies time = T
Time ? …..To
Time=T…..T1
Propagation time : (T1 – T0)/2
Client side clock = T + ( T1- T0)/2
CLOCK SYNCHRONIZATION ALGORITHMS
Active time server centralized algorithm

Time server broadcasts time to other nodes

Time = T
The other nodes adjust their time accordingly
Each node has a priori broadcast time knowledge
Ta[approx]
For propagation “time = T”
Time is T + Ta
Delays in broadcasts are major
The Berkeley Algorithm

Here thevtime server (actually, a time daemon) is

active, polling every machine from time to time to ask
what time it is there. Based on the answers, it computes
an average time and tells all the other machines to
advance their clocks to the new time or slow their
clocks down until some specified reduction has been
achieved.

The time daemon's time must be set manually by the

operator periodically.

13
14
EVENT ORDERING
Happened Before Relation (denoted by --> )
1. If a and b are events in same process, and a occurs
before b then a->b
2. If a is an event of sending a message by one process
and b is the event of receipt of same message by
another process,then a->b…receiver cannot receive
unless sender sends [Link] taken for the message
propogation from receiver to sender is always
positive.

3. If a -> b and b -> c,then a -> c,thus happened

before is a transitive relation.
LOGICAL CLOCKS CONCEPT
The concept of a logical clock is a way to
associate a timestamp (which maybe a
simple number independent of any clock
time)

Eg : Pi has a clock Ci associated with it that

assigns a number Ci(a) to any event a in that
process.
LAMPORT’S LOGICAL CLOCKS (2)
Figure 6-9. (a) Three processes, each with its own
clock.
The clocks run at different rates.
LAMPORT’S LOGICAL CLOCKS (3)

Figure 6-9. (b) Lamport’s algorithm corrects the clocks.

LAMPORT’S LOGICAL CLOCKS (4)

Figure 6-10. The positioning of Lamport’s logical

clocks in distributed systems.
IMPLEMENTATION OF LOGICAL CLOCKS
C1 : If a and b are two events within the same
process Pi and a occurs before b,then Ci(a)
<Ci(b)

C2 : If a is the sending of a message by

process Pi and b is the receipt of that
message by process Pj , then Ci(a) < Cj(b)

C3 : A clock Ci associated with a process Pi

must always go forward,never
[Link] is made by adding
value never subtracting it
IMPLEMENTATION OF LOGICAL CLOCKS
IR1 :Each process Pi increments Ci between
any two successive events

IR2 :If event a is the sending of a message m

by process Pi, the message m contains a
timestamp Tm = Ci (a) and upon receiving
the message m a process Pj sets Cj greater
than or equal to its present value but greater
than Tm.
VECTOR CLOCKS (1)

Figure 6-12. Concurrent message transmission

using logical clocks.
EXAMPLE: TOTALLY ORDERED
MULTICASTING

Figure 6-11. Updating a replicated database and

leaving it in an inconsistent state.
IMPLEMENTATION OF LOGICAL CLOCKS
Logical clocks can be implemented using :-

Counters

Physical clocks
Logical Clocks

In a distributed system, multiple machines are working together, and

each machine may have its own clock. still, these clocks may not be
accompanied with each other, and there's no single clock that can be
used to order events globally.

Logical clocks give a way to handle this by assigning each event a

logical timestamp, which can be used to order events and establish
reason between them, indeed if they do on different machines.

In substance, logical clocks give a way to produce a virtual global

timepiece that's consistent across all machines in a distributed system.
SCALAR TIME IMPLEMENTATION

There are different methods for implementing logical clocks in

a distributed system, but one of the simplest is Scalar Time.

In this implementation, each process keeps a local clock that

is initially set to 0. There are two rules for updating the local
clock −
Rule 1: Event Execution
Before executing an event (excluding the event of receiving a
message), increment the local clock by 1

Rule 2: Message Reception

When receiving a message (the message must include the
sender's local clock value), set your local clock to the
maximum of the received clock value and the local clock
value. After this, increment your local clock by 1.
Rule 1: Event Execution

local_clock = local_clock + 1

Rule 2: Message Reception

local_clock = max(local_clock,
received_clock) local_clock = local_clock
+1
28
Vector Clock

is an algorithm that generates partial ordering of events and

detects causality violations in a distributed system. These
clocks expand on Scalar time to facilitate a causally consistent
view of the distributed system, they detect whether a
contributed event has caused another event in the distributed
system. It essentially captures all the causal relationships.

This algorithm helps us label every process with a vector(a list

of integers) with an integer for each local clock of every
process within the system.

So for N given processes, there will be vector/ array of size N.

 How does the vector clock algorithm work?

• Initially, all the clocks are set to zero.

• Every time, an Internal event occurs in a process, the
value of the processes’s logical clock in the vector is
incremented by 1
• Also, every time a process sends a message, the value of
the processes’s logical clock in the vector is incremented
by 1.
• Every time, a process receives a message, the value of
the processes’s logical clock in the vector is incremented
by 1
• Moreover, each element is updated by taking the
maximum of the value in its own vector clock and the
value in the vector in the received message (for every
30
element).
31
MUTUAL EXCLUSION
 Fundamental to distributed systems is the concurrency
and collaboration among multiple processes. In many
cases, this also means that processes will need to
simultaneously access the same resources.
 To prevent that such concurrent accesses corrupt the

resource, or make it inconsistent, solutions are needed

to grant mutual exclusive access by processes.

 Distributed mutual exclusion algorithms can be

classified into two different categories. In token-
based solutions mutual exclusion is achieved by
passing a special message between the processes,
known as a token.
 There is only one token available and who ever has that33

token is allowed to access the shared resource.

When finished, the token is passed on to a next
process.
If a process having the token is not interested in

accessing the resource, it simply passes it on.

A Centralized Algorithm
The most straightforward way to achieve mutual. exclusion in a
distributed system is to simulate how it is done in a one-processor
system.
 One process is elected as the coordinator. Whenever a process
wants to access a shared resource, it sends a request message to
the coordinator stating which resource it wants to access and
asking for permission.
Ifno other process is currently accessing that resource, the
34
coordinator sends back a reply granting permission.
(a) Process 1 asks the coordinator for permission to
access a
shared resource. Permission is granted.
(b) Process 2 then asks permission to access the same
resource. The coordinator does not reply.
(c) When process 1 releases the resource, it tells the 35
coordinator, which then replies to 2.
 It is easy to see that the algorithm guarantees mutual
exclusion: the coordinator
 only lets one process at a time to the resource. It is also fair,
since requests are granted in the order in which they are
received. No process ever waits forever (no starvation). The
scheme is easy to implement, too, and requires only three
messages per use of resource (request, grant, release).

 The centralized approach also has shortcomings.

 The coordinator is a single point of failure, so if it crashes, the
entire system may go down.
 If processes normally block after making a request, they
cannot distinguish a dead coordinator from "permission
denied" since in both cases no message comes back.

36
 A Distributed Algorithm

 The algorithm works as follows. When a process wants to

access a shared resource, it builds a message containing the
name of the resource, its process number, and the current
(logical) time.
 It then sends the message to all other processes, conceptually
including itself. The sending of messages is assumed to be
reliable; that is, no message is lost.

 When a process receives a request message from another

process, the action it takes depends on its own state with
respect to the resource named in the message.

37
 Three different cases have to be clearly
distinguished:

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 me. one contained in the message that it has
sent everyone. The lowest one wins.
If the incoming message has a lower timestamp, the receiver
sends back an OK message. If its own message has a lower
timestamp, the receiver queues the incoming request and
sends nothing.

38
 After sending out requests asking permission, a process sits
back and waits until everyone else has given permission. As
soon as all the permissions are in, it may go ahead.
 When it is finished, it sends OK messages to all processes on its
queue and deletes them all from the queue.

39
(a) Two processes want to access a shared resource at the same
moment.
(b) Process 0 has the lowest timestamp. so it wins.
(c) When process 0 is done, it sends an OK also, so 2 can now go
ahead. Process 0 sends everyone a request with timestamp.

40
A TOKEN RING ALGORITHM

 Here we have a bus network, as shown in Fig. 6-16(a),

(e.g., Ethernet), with no inherent ordering of the processes.
In software, a logical ring is constructed in which each
process is assigned a position in the ring, as shown in Fig.
6-16(b).

 The ring positions may be allocated in numerical order of

network addresses or some other means. It does not
matter what the ordering is. All that matters is that each
process knows who is next in line after itself.

41
 As usual, this algorithm has problems too. If the token is
ever lost, it must be regenerated. In fact, detecting that it
is lost is difficult, since the amount of time between
successive appearances of the token on the network is
unbounded. The fact that the token has not been spotted
for an hour does not mean that it has been lost; somebody
may still be using it.

42
ELECTION ALGORITHMS

 Many distributed algorithms require one process to

act as coordinator, initiator, or otherwise perform
some special role. In general, it does not matter which
process takes on this special responsibility, but one of
them has to do it. In this section we will look at
algorithms for electing a coordinator.

 In general, election algorithms attempt to locate the

process with the highest process number and
designate it a coordinator.

43
THE BULLY ALGORITHM

 When any process notices that the coordinator is no longer

responding to requests, it initiates an election. A process,
 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. P, holds an election as follows:

44
A Ring Algorithm

45
Exercise 2

Explain "call by reference" vs. "call by value".

How does so called marshalling solve the problem of different byte

ordering of sender and receiver?

46