Importance Of Time In Distributed Systems

Time is an important and interesting issue in Distributed Systems for several reasons. First, time is a quantity we always want to measure accurately. In order to know at what time of day a particular event occurred at a particular computer, it is necessary to synchronize its clock with an authoritative, external source of time. Second, algorithms that depend upon clock synchronization have been developed for several problems in distribution; these include maintaining the consistency of distributed data, checking the authenticity of a request sent to a server and eliminating the processing of duplicate updates [1]

In Centralized systems, there is no need for clock synchronization because, generally, there is only a single clock. A process gets the time by simply issuing a system call to the kernel.

When another process after that tries to get the time, it will get a higher time value. Thus, in such systems, there is a clear ordering of events and there is no ambiguity about the times at which these events occur. [4]

In Distributed systems, there is no global clock or common memory. Each processor has its own internal clock and its own notion of time. In practice, these clocks can easily drift apart by several seconds per day, accumulating significant errors over time. Also, because different clocks tick at different rates, they may not remain always synchronized although they might be synchronized when they start. This clearly poses serious problems to applications that depend on a synchronized notion of time.

Distributed systems are subject to timing uncertainties as certain processes may lack a common notion of real time. Due to an uncertainty in message delay time, absolute process synchronization is known to be impossible for such systems

The literature presents issues of timing in distributed systems, physical clocks and their synchronization problems, algorithms for synchronizing physical clocks are presented with their limitations, and also techniques for implementing logical clocks which are used to monitor the order of events without measuring the physical time at which the events occurred

The concept of time

Let us begin by asking this simple question; does anybody really know what time it is [3]

As Lamport notes, the concept of time is fundamental to our way of thinking [7] In fact, real time helps to master many problems of our decentralized real world. Time is also a useful concept when considering possible causality. Consider a person suspected of a crime, if that person has an alibi because he or she was far enough away from the site of the crime at some instant close enough to the time of the crime, then he or she cannot be the culprit.

Timing problems

Accurate time is important to determining the order in which events occur; [3] this is a basic standard of transactional integrity, system and network‐wide logging, auditing, troubleshooting and forensics. Having an accurate time source plays a critical role in tracing and debugging problems that occur on different platforms across a network. Events must be correlated with each other regardless of where they were generated. Furthermore, the notion of time (or time ranges) is used in many forms of access control, authentication, and encryption. In some cases, these controls can be bypassed or rendered inoperative if the time source could be manipulated. For example, a payroll function could be tricked into providing access over a weekend when normally it would be restricted to normal business hours. [3]

Physical clocks

Most computers today keep track of the passage of time with a battery-backed up Complementary Metal Oxide Semiconductor (CMOS) clock circuit, driven by a quartz resonator. This allows the timekeeping to take place even if the machine is powered off. When on, an operating system will generally program a timer circuit (a Programmable Interval Timer, or PIT, in older Intel architectures and Advanced Programmable Interrupt Controller, or APIC, in newer systems.) to generate an interrupt periodically (common times are 60 or 100 times per second). The interrupt service procedure simply adds one to a counter in memory. While the best quartz resonators can achieve an accuracy of one second in 10 years, they are sensitive to changes in temperature and acceleration and their resonating frequency can change as they age. Standard resonators are accurate to 6 parts per million at 31°C, which corresponds to ±½ second per day.

The problem with maintaining a concept of time is when multiple entities expect each other to have the same idea of what the time is. Two watches hardly ever agree. Computers have the same problem: a quartz crystal on one computer will oscillate at a slightly different frequency

than on another computer, causing the clocks to tick at different rates. The phenomenon of clocks ticking at different rates, creating an ever widening gap in perceived time is known as clock drift. The difference between two clocks at any point in time is called clock skew and is due to both clock drift and the possibility that the clocks may have been set differently on different machines. The Figure below illustrates this phenomenon with two clocks, A and B, where clock B runs slightly faster than clock A by approximately two seconds per hour. This is the clock drift of B relative to A. At one point in time (five seconds past five o'clock according to A's clock), the difference in time between the two clocks is approximately four seconds. This is the clock skew at that particular time.

Compensating for drift

We can envision clock drift graphically by considering true Coordinated Universal Time (UTC) flowing on the x-axis and the corresponding computer's clock reading on the y-axis. A perfectly accurate clock will exhibit a slope of one. A faster clock will create a slope greater than unity while a slower clock will create a slope less than unity. Suppose that we have a means of obtaining the true time. One easy (and frequently adopted) solution is to simply update the system time to the true time. To complicate matters, one constraint that we'll impose is that it's not a good idea to set the clock back. The illusion of time moving backwards can confuse message ordering and software development environments.

If a clock is fast, it simply has to be made to run slower until it synchronizes. If a clock is slow, the same method can be applied and the clock can be made to run faster until it synchronizes. The operating system can do this by changing the rate at which it requests interrupts. For example, suppose the system requests an interrupt every 17 milliseconds (pseudo-milliseconds, really - the computer's idea of what a millisecond is) and the clock runs a bit too slowly. The system can request interrupts at a faster rate, say every 16 or 15 milliseconds, until the clock catches up. This adjustment changes the slope of the system time and is known as a linear compensating Function. After the synchronization period is reached, one can choose to resynchronize periodically and/or keep track of these adjustments and apply them continually to get a better running clock. This is analogous to noticing that your watch loses a minute every two months and making a mental note to adjust the clock by that amount every two months (except the system does it continually).

Synchronizing physical clocks

With physical clocks, our interest is not in advancing them just to ensure proper message ordering, but to have the system clock keep good time. We looked at methods for adjusting the clock to compensate for skew and drift, but it is essential that we get the time first so that we would know what to adjust. One possibility is to attach a GPS (Global Positioning System) receiver to each computer. A GPS receiver will provide time within ± 1 msec. of UTC time but

Unfortunately, they rarely work indoors. Alternatively, if the machine is in the U.S., one can attach a WWV radio receiver to obtain time broadcasts from Texas, Colorado or Washington, DC, giving accuracies of ± 3-10 msec. depending on the distance from the source. Another option is to obtain a GOES (Geostationary Operational Environment Satellites) receiver, which will provide time within ± 0.1 msec. of UTC time.

For reasons of economy, convenience, and reception, these are not practical solutions for every machine. Most machines will set their time by asking another machine for the time (preferably one with one of the aforementioned time sources). A machine that provides this information is called a time server. Several algorithms have been proposed for synchronizing clocks and they all have the same underlying model of the system

Cristian's algorithm

The simplest algorithm for setting the time would be to simply issue a remote procedure call to a time server and obtain the time. That does not account for the network and processing delay. We can attempt to compensate for this by measuring the time (in local system time) at which the request is sent (T0) and the time at which the response is received (T1). Our best guess at the network delay in each direction is to assume that the delays to and from are symmetric (we have no reason to believe otherwise). The estimated overhead due to the network delay is then (T1- T0)/2. The new time can be set to the time returned by the server plus the time that elapsed since the server generated the timestamp:

Suppose that we know the smallest time interval that it could take for a message to be sent between a client and server (either direction). Let's call this time Tmin. This is the time when the network and CPUs are completely unloaded. Knowing this value allows us to place bounds on the accuracy of the result obtained from the server. If we sent a request to the server at time T0, then the earliest time stamp that the server could generate the timestamp is T0 + Tmin. The latest time that the server could generate the timestamp is T1 - Tmin, where we assume it took only the minimum time, Tmin, to get the response. The range of these times is: T1 - T0 - 2Tmin, so the accuracy of the result is:

Errors are cumulative. If machine A synchronizes from a server B and gets an accuracy of ±5 msec but server B in turn got its time from server C with an accuracy of ±7 msec, the net accuracy at machine A is ±(5+7), or ±12 msec. Several time requests may be issued consecutively in the hope that one of the requests may be delivered faster than the others (e.g., it may be submitted during a time window when network activity is minimal). This can achieve improved accuracy. Cristian's algorithm suffers from the problem that afflicts all single-server algorithms: the server might fail and clock synchronization will be unavailable. It is also subject to malicious interference.

Berkeley algorithm

The Berkeley algorithm, developed by Gusella and Zatti in 1989 [8], is form of an internal synchronization that does not assume that any machine has an accurate time source with which to synchronize. Instead, it opts for obtaining an average time from the participating computers and synchronizing all machines to that average. The machines involved in the synchronization each run a time dæmon process that is responsible for implementing the protocol. One of these machines is elected (or designated) to be the master. The others are slaves. The server polls each machine periodically, asking it for the time. The time at each machine may be estimated by using Cristian's method to account for network delays. When all the results are in, the master computes the average time (including its own time in the calculation). The hope is that the average cancels out the individual clock's tendencies to run fast or slow. Instead of sending the updated time back to the slaves, which would introduce further uncertainty due to network delays, it sends each machine the offset by which its clock needs adjustment. The operation of this algorithm is illustrated in the Figure below. Three machines have times of 3:00, 3:25, and 2:50. The machine with the time of 3:00 is the server (master). It sends out a synchronization query to the other machines in the group.

Each of these machines sends a timestamp as a response to the query. The server now averages the three timestamps: the two it received and its own, computing (3:00+3:25+2:50)/3 = 3:05. Now it sends an offset to each machine so that the machine's time will be synchronized to the average once the offset is applied. The machine with a time of 3:25 gets sent an offset of -0:20 and the machine with a time of 2:50 gets an offset of +0:15. The server has to adjust its own time by +0:05. The algorithm also has provisions to ignore readings from clocks whose skew is too great. The master may compute a fault-tolerant average - averaging values from machines whose clocks have not drifted by more than a certain amount. If the master machine fails, any other slave could be elected to take over

Logical clocks

Let's again consider cases that involve assigning sequence numbers ("timestamps") to events upon which all cooperating processes can agree. What matters in these cases is not the time of day at which the event occurred but that all processes can agree on the order in which related events occur. Our interest is in getting event sequence numbers that make sense system-wide. If we can do this across all events in the system, we have something called total ordering: every event is assigned a unique timestamp (number), every such timestamp is unique. However, we don't always need total ordering. If processes do not interact then we don't care when their events occur. If we only care about assigning timestamps to related (causal) events then we have something known as partial ordering.

Leslie Lamport [7] developed a "happened before" notation to express the relationship between events: a→b means that a happened before b. If a represents the timestamp of a message sent and b is the timestamp of that message being received, then a→b must be true; a message cannot be received before it is sent. This relationship is transitive. If a→b and b→c then a→c. If a and b are events that take place in the same process the a→b is true if a occurs before b.

The importance of measuring logical time is in assigning a time value to each event such that everyone will agree on the final order of events. That is, if a→b then clock (a) < clock (b) since the clock (our timestamp generator) must never run backwards. If a and b occur on different

Processes that do not exchange messages (even through third parties) then a→b is not true, these events are said to be concurrent: there is no way that a could have influenced b.

Each event is assigned a timestamp by its respective process. The process simply maintains a global counter that is incremented before each event gets a timestamp.

If we examine the timestamps from our global perspective, we can observe a number of peculiarities. Event g, the event representing the receipt of the message sent by event a, has the exact same timestamp as event a when it clearly had to take place after event a. Event e has an earlier time stamp (1) than the event that sent the message (b, with a timestamp of 2).

Lamport's algorithm

Lamport [7] proposed an algorithm that forces the resequencing of timestamps to ensure that the happened before relationship is properly depicted for events related to sending and receiving messages. It works as follows:

Each process has a clock, which can be a simple counter that is incremented for each event.

The sending of a message is an event and each message carries with it a timestamp obtained from the current value of the clock at that process (sequence number).

The arrival of a message at a process is also an event will also receive a timestamp - by the receiving process, of course. The process' clock is incremented prior to time stamping the event, as it would be for any other event. If the clock value is less than the timestamp in the received message, the system's clock is adjusted to the (message's timestamp + 1). Otherwise nothing is done. The event is now time stamped.

If we apply this algorithm to the same sequence of messages, we can see that proper message ordering among causally related events is now preserved. Note that between every two events, the clock must tick at least once. [4]

Lamport's algorithm [7] allows us to maintain proper time ordering among causally- related events. In summary, Lamport's algorithm requires a monotonically increasing software counter for a "clock" that has to be incremented at least when events that need to be time stamped take place. These events will have the clock value, or "Lamport timestamp," associated with them. For any two events, where a→b, L (a) < L (b) where L(x) represents the Lamport timestamp for event x.

Lamport timestamps [7] assure us that if there is a causal relationship between two events, then the earlier event will have a smaller time stamp than the later event. Causality is achieved by successive events on one process or by the sending and receipt of messages on different processes. As defined by the happened-before relationship, causality is transitive. For instance, events a and f are causally related in the figure above (through the sequence a, b, e, f).

Implementing Logical clocks

To implement logical clocks, [11] each process p, maintains data structures that give it the following two capabilities:

A logical clock, denoted by C, that helps P, measure its own progress; and

A global logical clock denoted by gC, that represents Ps local view of the global logical time.

A protocol is presented to update the data structures; the protocol ensures that a process's logical clock and its view of the global time are consistent. The protocol consists of the following two rules:

R1. - maintains how a process updates the local logical clock when it executes an

Event, whether send or receive

R2. - maintains how a process updates its global logical clock to update its view of the

Global time. It dictates what information about the logical time a process

Piggybacks in a message and how the receiving process uses this information to

Update its view of the global time

A distributed system consisting of logical clocks differ in their representation of logical time and in the protocol for updating logical clocks. However, all systems consisting of logical clocks implements some form of R1 and R2 and thereby achieving the fundamental monotonicity property associated with events and casualty

Total ordering of events

Note that it is very possible for multiple non-causal (concurrent) events to share identical Lamport timestamps (e.g., c, e, and h in the Figure above). This may cause confusion if multiple processes need to make a decision based on the timestamps of two events.

The selection of a specific event may not matter if the events are concurrent but we want all the processes to be able to make the same decision. This is difficult if the timestamps are identical. Fortunately, there's an easy remedy. We can create a total order on events by further qualifying them with identities of processes. We define a global logical timestamp (Ti,i) where Ti represents the local Lamport timestamp and i represents the process ID (in some globally unique way: for example, a concatenation of host address and process ID). We are then able to globally compare these timestamps and conclude that

There is no physical significance to the order since process identifiers can be arbitrary and do not relate to event ordering but the ability to ensure that no two Lamport timestamps are the same globally is helpful in algorithms that need to compare these timestamps. In real life, depending on the application, one may use a combination of thread ID, process ID, and IP address as a qualifier to the timestamp.

Vector clocks

If two events are causally related and event e happened before event e' then we know that L (e) < L (e'). However, the converse is not necessarily true. With Lamport's algorithm, if L (e) < L (e') we cannot conclude that e→e'. Hence, if we look at Lamport timestamps, we cannot conclude which pairs of events are causally related and which are not.

One solution that has been proposed to deal with this problem is the concept of vector clocks (proposed by Mattern in 1989 and Fidge in 1991) [9, 10]. A vector clock in a system of N processes is a vector of N integers. Each process maintains its own vector clock (Vi for a process Pi) to timestamp local events. Like Lamport timestamps, vector timestamps (the vector of N integers) are sent with each message. The rules for using vector clocks are:

The vector is initialized to 0 at all processes: Vi[j] = 0 for i,j = 1, …, N

Before a process Pi timestamps an event, it increments its element of the vector in its local vector: Vi[i] = Vi[i]+1

A message is sent from process Pi with Vi attached to the message.

When a process Pj receives a vector timestamp t, it compares the two vectors element by element, setting its local vector clock to the higher of the two values: Vj[i] = max(Vj[i], t[i]) for i=1, …, N

We compare two vector timestamps by defining:

V = V' iff V[j] = V'[j] for i=1, …, N

V ≤ V' iff V[j] ≤ V'[j] for i=1, …, N

For any two events e, e', if e→e' then V(e) < V(e'). This is the same as we get from Lamport's algorithm. With vector clocks, we now have the additional knowledge that if V(e) <V(e') then e→e'. Two events e, e' are concurrent if neither V(e) ≤ V(e') nor V(e') ≤ V(e).

The disadvantage with vector clocks is the greater storage and message payload size, since an entire vector rather than a single integer must be manipulated.

Conclusion

This literature review began by describing the importance and issues of proper time ordering for distributed systems. It further described two algorithms for the synchronization of physical clocks in distributed systems with respect to external time source, which are a result of clock drift because no two clocks can ever agree. Lamport's algorithm, the happened before relation tends to impose a partial order on events that reflects the passage of messages between them which allow us to maintain proper time ordering among causally-related events,

Vector clocks have been introduced as an improvement on Lamport clocks reason being because by examining the timestamps, it is possible to determine whether two events are concurrent or are ordered by the happened before relation