PA160: Net-Centric Computing II. Time Synchronization
Luděk Matýska
Faculty of Informatics Masaryk University
Spring 2016
Luděk Matýska (Fl MU)
4. Time Synchronization
Spring 2016       1 /
Time on a single node
Timer (clock)
• Oscillating quartz crystal 9 Counter
• Each oscillation decreases the counter value
• Interrupt when zero
Each individual interrupt is a tick
• Holding register
• Counter initiation after interrupt
9 Stored time increased after each interrupt
Luděk Matýska (Fl MU) 4. Time Synchronization Spring 2016       2 /1
Distributed computer systems
<* Each node has its own timer
• Time is not automatically synchronized
• Clock skew
• Relation to the absolute time 9 Problems
• Internode synchronization
• Absolute time synchronization
Luděk Matýska (Fl MU) 4. Time Synchronization Spring 2016       3 /1
Absolute time
• Original (old) definition of the time unit
• 1 second equals 1/86 400 solar day
• Current definition of the time unit—atomic clock
• Electronic transition frequency of the electromagnetic spectrum of atoms
o Cesium-133 standard in 1955
• Chip-scale atomic clock in 2004 (125 mW)
• 1 second equals 9192 631770 cycles (transitions between two energ levels of Cs-133)
• International atomic clock
• Average measurement of around 50 world laboratories
Luděk Matýska (Fl MU)
4. Time Synchronization
Spring 2016
niversal 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
a UTC globally synchronized
Luděk Matýska (Fl MU)
4. Time Synchronization
Spring 2016       5 /
Clock synchronization
• Basic assumptions
• A set of nodes with their own clocks/timers
• Interrupt frequency H Hz
Cp(t) is the time measured by clock at node p
• Ideally Cp(t) = t for all p
• Real behavior: If there exists p such as
i-p<^<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 (Fl MU) 4. Time Synchronization Spring 2016       6 /1
Cristian's algorithms
9 We have a time server
9 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 (Fl MU) 4. Time Synchronization Spring 2016       7 /1
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 9 We "stop" the time
• Small—communication delay
o Measure the time of sending (Tq) and receiving (7~i) the request
• Add time of the transfer (Tq + 7~i)/2
• Correct for the time spent at the server (request processing), if known
Luděk Matýska (Fl MU) 4. Time Synchronization Spring 2016       8 /1
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
Decentralized solutions
• Re-synchronization intervals
• A starting point Tq globally agreed
• Interval / starts at the time Tq + iR
• Interval / ends at the time 7~o + (' + 1)R
• 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 (Fl MU)
4. Time Synchronization
Spring 2016
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 (Fl MU) 4. Time Synchronization Spring 2016       11 / 1
Logical time
• Absolute time is not always necessary
9 Relative time (relation between events) often more important
• Logical time
• No need for absolute synchronization
• Need agreement on the order
Luděk Matýska (Fl MU) 4. Time Synchronization Spring 2016 12/1
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
o a —>* b is transitive
• Events x and y are concurrent iff nor x —>* y nor y —>* x holds
Luděk Matýska (Fl MU) 4. Time Synchronization Spring 2016 13/1
Implementation
• Each process does have its own logical clock
• 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 7~s 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 = 7~s + 1
• Additional condition
• No two events happen at the same time
Luděk Matýska (Fl MU)
4. Time Synchronization
Spring 2016        14 /
Summary
• Lamport's algorithm is sufficient to define and keep a global (logica 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 a ^ b, C(a) 7^ 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 in Computer Science of all time
Luděk Matýska (Fl MU)
4. Time Synchronization
Spring 2016