FACULTY OF INFORMATICS Masaryk University PA160: Net-Centric Computing II. Time Synchronization Luděk Matýska Spring 2023 Luděk Matýska • Time Synchronization • Spring 2023 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 2023 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 2023 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 2023 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 2023 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► 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 2023 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 2023 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 2023 15/