FACULTY
OF INFORMATICS
Masaryk University
PA160: Net-Centric Computing II. Time Synchronization
Luděk Matýska
Spring 2024
Luděk Matýska • Time Synchronization • Spring 2024
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Time on a single node
■ Timer (dock)
■ Oscillating quartz crystal
■ Counter
■ Each oscillation decreases the counter value
■ Interrupt when zero
Each individual interrupt is a tick
■ Holding register
■ Counter initiation after interrupt
■ Stored time increased after each interrupt
Luděk Matýska • Time Synchronization • Spring 2024
2/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Distributed computer systems
■ Each node has its own timer
■ Time is not automatically synchronized
■ Clock skew
■ Relation to the absolute time
■ Problems
■ Internode synchronization
■ Absolute time synchronization
Luděk Matýska • Time Synchronization • Spring 2024
3/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Absolute time
■ Original (old) definition of the time unit
■ 1 second equals 1/86400 solar day
■ Current definition of the time unit-atomic clock
■ Electronic transition frequency of the electromagnetic spectrum of atoms
■ Cesium-133 standard in 1955
■ Chip-scale atomic clock in 2004 (125 mW)
■ 1 second equals 9192 631 770 cycles (transitions between two energy levels of Cs-133)
■ International atomic clock
■ Average measurement of around 50 world laboratories
Luděk Matýska • Time Synchronization • Spring 2024
4/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Universal Coordinated Time, UTC
■ Atomic and soLar times are not synchronized
■ Leap second needed
■ Compensation for the irregularities of Earth rotation
■ Added whenever difference between atomic clock and mean solar time gets 800 ms
■ Result is the Universal Coordinated Time (UTC)
■ GMT replacement
■ UTC globally synchronized
Luděk Matýska • Time Synchronization • Spring 2024
5/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Clock synchronization
■ Basic assumptions
■ A set of nodes with their own clocks/timers
■ Interrupt frequency H Hz
Cp(t) is the time measured by dock at node p
■ Ideally Cp(t) = t for all p
■ Real behavior: If there exists p such as
i-p<w<i+p
then clock Cp works with the specification p
■ p is defined by the clock producer (it is the maximal time skew)
■ If we are looking for a clock synchronization with the highest difference 5, then the synchronization must occur at most every S/2p seconds
Luděk Matýska • Time Synchronization • Spring 2024
6/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Cristian's algorithms
■ We have a time server
■ synchronized with UTC
■ Each S/2p each node sends a request to the server
■ Server replies with its own (UTC) time (as fast as possible)
■ Naive solution: the node modifies its time accordingly
Luděk Matýska • Time Synchronization • Spring 2024
7/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Problems
■ Important-deLay compensation
■ Time stops to have linear course (shape)
■ Unexpected and undesirable effects
■ Time cannot move "backwards"
■ Solution
■ The absolute time is not increased at the interrupt
■ We "stop" the time
■ Small-communication delay
■ Measure the time of sending (7b) and receiving (7i) the request
■ Add time of the transfer (7b + 7"i)/2
■ Correct for the time spent at the server (request processing), if known
Luděk Matýska • Time Synchronization • Spring 2024
8/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Berkeley algorithm
■ Active time server
■ Periodically queries nodes for their absolute time
■ Averages node times
■ Sends this new time to all nodes
■ Suitable if no access to UTC source exists
■ Analogy of UTC-time based on the agreement of the nodes
Luděk Matýska • Time Synchronization • Spring 2024
9/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Decentralized solutions
■ Re-synchronization intervals
■ A starting point 7"0 globally agreed
■ Interval / starts at the time To + iR
■ Interval / ends at the time 7"0 + (/ + 1)R m R is an agreed system parameter
■ ALL nodes broadcast their absolute time at the beginning of each interval
■ Each node does the following
■ Receives S messages
■ Computes the average (with the removal of m outliers)
■ Improvement possible if the message propagation delay known
Luděk Matýska • Time Synchronization • Spring 2024
10/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
NTP
■ Network Time Protocol
■ Version 3 (RFC1305), version 2 (RFC1119), version 1 (RFC 1059)
■ S(imple)NTP: RFC 1769
■ Hierarchical structure based on Stratums
■ Stratum 1 directly connected to UTC (atomic clock,...)
■ Stratum / + 1 connects to server(s) at Stratum /
■ Up to 16 levels (Stratum 16)
■ Highly scalable
■ More than one server
■ Tolerant to server fault of precision loss
■ Servers tik. cesnet. cz and tak. cesnet. cz
Luděk Matýska • Time Synchronization • Spring 2024
11/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Logical time
■ Absolute time is not always necessary
■ Relative time (relation between events) often more important
■ Logical time
■ No need for absolute synchronization
■ Need agreement on the order
Luděk Matýska • Time Synchronization • Spring 2024
12/15
Time on a single node
FACULTY
OF INFORMATICS
Masaryk University
Lamport timestamps
■ Relation "happens-before"
■ a —>► b means that all processes agree that a happened before b
■ If a represents an event of sending a particular message and b represents the receipt of the same message, then a —>► b holds
■ Properties
■ a —>► b is transitive
■ Events x and y are concurrent iff nor x —>► y nor y —>► x holds
Luděk Matýska • Time Synchronization • Spring 2024
13/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Implementation
■ Each process does have its own Logical dock
■ For events within any particular process the relation "happens-before" is trivially fulfilled
■ Interprocess synchronization is the result of message passing
■ Each message contains time stamp Ts of the sender (its time of sending the message)
■ If internal receiver time Tr is lower (i.e. "younger") than the time of sending the message (7"s), we put Tr = Ts + 1
■ Additional condition
■ No two events happen at the same time
Luděk Matýska • Time Synchronization • Spring 2024
14/15
Time on a single node
FACULTY
OF INFORMATICS
I   Masaryk University
Summary
■ Lamport's algorithm is sufficient to define and keep a global (Logical) time in a distributed system
■ Properties
■ If a happens before b in the same process, C(a) < C(b)
■ If a is sending and b receipt of the same message, C(a) < C(b)
■ For all events a, b such that        C(a) ^ C(b) holds
■ The algorithms provides global (partial) order on events in a distributed system
■ First published in 1978 in CACM; one of the most cited articles Computer Science of all time
Luděk Matýska • Time Synchronization • Spring 2024
15/