• View
• Edit
• History
• Print

Time in Distributed Systems

A Distributed Computing Lecture by Steven Choy

Acknowledgement: Some of the materials in this lecture are based on Chapter 11: Time and Global State in 'Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edition 4 (the website for the book is http://www.cdk4.net/). Please refer to this chapter of the textbook.

Introduction

Time in Distributed Systems

• Time is important. Why?
• However, it is problematic in distributed systems. Why?
• We want to know when something happened.
• Algorithms may depend upon clock synchronization.
• No global notion of time.

Clocks, Events, and Process States

• We define an event to be the occurrence of a single action that a process carries out as it executes.
• An event is a communication action or a state-transforming action.
• Clocks — every computer has one, and it can be used to timestamp any event.

System Model

• N processes in a distributed system:
  • Each executes on a single processor.
  • No shared memory.
  • The only communication means is exchange of messages.
• p_i has state s_i.
• An event is the occurrence of a single action
  • An internal state-transforming action by p_i, or
  • a communication action
• e →_i e' iff e occurs before e’ in p_i

Clock Skew

• Each computer has its own physical clock.
• The software clock C_i can be used to timestamp any event at p_i.
• Problems: Clock skew and clock drift.

Coordinated Universal Time (UTC)

• International standard for timekeeping
• Based on atomic time
• Synchronizes with astronomical time using leap seconds
• UTC signals are synchronized and broadcast regularly from land-based radio stations and satellites.
• Computers with receivers attached can synchronize their clocks with these timing signals.

Synchronizing physical clocks

Basics

• External synchronization:
  • setting the time to some external source of time
  • For each i, synchronize C_i with an authoritative, external source of time.
• Internal synchronization:
  • setting the time based on "local agreement" (local time)
  • For each i,j, synchronize C_i and C_j with each other
• Three typical methods of synchronization
  • Cristians algorithm.
  • The Berkeley algorithm.
  • Network time protocol (NTP).

Cristian’s Algorithm

• Basic idea - Getting the current time from a "time server", using periodic client requests

• Major problem – what happens if the time from the 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
• Procedures:

• Accuracy: ± (T_round / 2 - min)
  T_round is the round trip time recorded by p
  min is an estimated minimum message transmission time
  • because the earliest time S puts t in message m_t is min after p sent m_r
  • the latest time was min before m_t arrived at p
  • the time by S’s clock when m_t arrives is in then: [ t + min, t + T_round - min ]

Class Exercise

• A client attempts to synchronize with a time server. It records the round-trip times and timestamps returned by the server in the table below.

   Round-trip time: 22ms; Time: 10:54:23.674
   Round-trip time: 25ms; Time: 10:54:25.450
   Round-trip time: 20ms; Time: 10:54:28.342

• Question 1: Which of these times should it use to set its clock? To what time should it set it?
• Question 2: Estimate the accuracy of the setting with respect to the server’ clock.
• Question 3: If it is known that the time between sending and receiving a message in the system concerned is at least 8 ms, do your answers change?
• Answers : The client should choose the minimum round-trip time of 20 ms = 0.02 s. It then estimates the current time to be 10:54:28.342 + 0.02/2 = 10:54:28.352. The accuracy is ± 10 ms. If the minimum message transfer time is known to be 8 ms, then the setting remains the same but the accuracy improves to ± 2 ms.

The Berkeley algorithm

• Internal synchronization
• A coordinator computer chosen to act as master
• Master periodically polls the other computers (the slaves)
• Slaves send back their clock values to master
• Master calculates an average (taking the roundtrip times into account)
• Master sends the amount by which each individual slave’s clock requires adjustment
• The algorithm eliminates readings from faulty clocks

The Network Time Protocol (NTP)

• The most used clock synchronization solution on the internet is the Internet Network Time Protocol (NTP) which is a layered client-server architecture based on UDP message passing.
• The Network Time Protocol (NTP) is a protocol for synchronizing the clocks of computer systems over packet-switched, variable-latency data networks. NTP uses UDP port 123 as its transport layer. It is designed particularly to resist the effects of variable latency

Experience NTP

      net time /setsntp:"0.pool.ntp.org 1.pool.ntp.org 2.pool.ntp.org"
      net time /set

NTP Design Goals

• To provide a service enabling clients across the Internet to be synchronized accurately to UTC
• To provide a reliable service that can survive lengthy losses of connectivity
• To enable clients to resynchronize sufficiently frequently to offset the rates of drift found in most computers
• To provide protection against interference with the time service, whether malicious or accidental

How NTP Works

• Provides a network of servers located across the Internet
• Primary servers attached to a UTC time source
• Secondary servers connected to a primary server for synchronization
• The servers are connected in a logical hierarchy called a "synchronization subnet", whose levels are called "strata"
• The synchronization subnet can reconfigure when servers become unreachable or failures occur
• Messages are delivered using UDP
• Some illustrations: From wikipedia, from usno.navy.mil, from process.com

Logical Clock and Vector Clock

Logical Clocks

• Synchronization is 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.

Idea on Lamport Logical Clock

• 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
• 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

• 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
• Obviously, if A “happens-before” B and B “happens-before” C, then it follows that A “happens-before” C
• If the “happens-before” relation holds, deductions about the current clock “value” on each distributed system component can then be made
• It therefore follows that if C(A) is the time on A, then C(A) is less than C(B), and so on
• Now, assume three processes are in a distributed system: A, B and C
• All have their own physical clocks (which are running at differing rates due to “clock skew”, etc.)
• 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 “happensbefore” relation still holds (i.e. A “happensbefore” B is true)
• However, if the timestamp is more than the time of arrival at B, things are NOT OK (as A “happensbefore” B is not true, and this cannot be as the receipt of a message has to occur after it was sent)
• The question to ask is: How can some event that “happens-before” some other event possibly have occurred at a later time?
• The answer is: it can’t!
• So, Lamport’s solution is 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 logical clocks and timestamps

• A Lamport logical clock is a monotonically increasing software counter.
• Each process p_i keeps its own logical clock L_i which is used to apply Lamport timestamps to events.
• To capture the happened-before relation → , processes update their logical clocks and transmit the values of their logical clocks in messages as follows:
  • Before each event at p_i: L_i := L_i + 1
  • When p_i sends a message m, it piggybacks t=L_i
  • When p_j receives (m,t): L_j := max(L_j,t) + 1
• e → e’ => L(e) < L(e’)
• Example

• More Examples from the Web

Vector Timestamps

• Observation: Lamport timestamps do not guarantee that if C(a) < C(b) that a indeed happened before b.
• We need vector timestamps for that.
• Each process P_i has an array V_i[1...n] , where V_i[j] denotes the number of events that process P_i knows have taken place at process P_j.
• When P_i sends a message m, it adds 1 to V_i[i], and sends V_i along with m as vector timestamp v_t(m). Result: upon arrival, each other process knows P_i’s timestamp.

• The simple rules for updating the vector clocks:
  • Initially, V_i[j] = 0 for i, j = 1, 2..., N
  • Just before p_i timestamps an event, it sets V_i[i] := V_i[i] + 1
  • p_i includes the value t = V_i in every message it sends
  • When p_i receives a timestamp t in a message, it sets V_i[j] := max(V_i[j], t[j]), for j = 1, 2...,N. Taking the component-wise maximum of two vector timestamps in this way is known as a merge operation.

Ordering with Vector Timestamps

• Lamport clock: e₁ → e₂ => C(e₁) < C(e₂)
• Vector Clock: e₁ → e₂ => V(e₁) < V(e₂) and V(e₁) < V(e₂) => e₁ → e₂

Some Examples

• Google 'Vector Timestamps'

Thanks for Reading

If you would rather like to have this lecture note in printed format, please click the print action link in the top right corner.

If you find any problem in this lecture note, please feel free to reach Steven by steven@findaway.hk