Time, Clocks, and the Ordering of Events in a Distributed System
Leslie Lamport

Lamprot in this paper examines the concept of temporal ordering of
events in a distributed system which consists of a collection of
distinct spatially separated processes and coordinates its operation
by exchanging messages. The relation "happened-before" can only
order the events happen in a distributed system partially since it is
sometimes impossible to differentiate from two events which one
happens first. Any two distinct events occur in the same process can
be ordered by the relation "happened-before". The event of
sending a message from a process must be "happened-before" of
receiving this message by another process. If two events can’t be
related by the relation "happened-before" they said to be
concurrent. The happened-before can’t be defined using real clocks
because they are not perfectly accurate and do not keep precise
physical times. Ordering can’t cope with the limited precision of
hardware clocks, their drifts or even the synchronization error
accuracy.

Logical clocks are used as a way to order the events in distributed
systems. Logical clocks are a set of functions, written as C(event),
that map each event in all the processes to the set of
integers. Therefore they can be implemented using counters with no
actual timing mechanism. These counters have to satisfy one
condition. If a and b are two events in a system and a happened-before
b then C(a) has to be less than C(b). To hold this condition two cases
can arise. (1) The two a and b events happen in the same process i, in
this case the process i increments the clock Ci between any two
successive events so Ci(a) < Ci(b). (2) The event a is sending the
message m event from process i to process j so in this case process i
timestamps the message with its own logical clock Tm=Ci(a). When
process j receives the message m, it sets its clock to the Cj(b)
greater than or equal to its present value and greater Tm. It worthy
noting that changing the logical clock C does not itself constitute an
event.

With this partial ordering two events in the system can be
time-stamped with the same value. Some interesting problems might need
ordering the events totally for example the mutual exclusion
problem. Ordering the events totally can be done by breaking the ties
encountered with concurrent events. The timestamps of the logical
clocks can be extended to include the process identifier. In this case
a happened-before b if Ci(a) < Cj(b) or Ci(a) = Cj(b) and i < j.

Lamport’s logical clocks have three shortcomings. (1) From the fact
that Ci(a) < Cj(b) no one can conclude that a happned-before
b. Mattern and Fidge developed vector clocks to overcome this
shortcoming. A vector clock is very similar to the one that Lamport
used but it includes a different clock for each process. This vector
is used to timestamp each message exchanged in the system. This vector
clock consumes a considerable storage in the system and increases the
size of the payload attached with each message. (2) With logical
clocks, a distributed system may encounter anomalous behaviors because
logical clocks do not consider external events to part of their event
sets. (3) A process failure is a very difficult problem to handle with
logical clocks. The concept of failure is only meaningful in the
context of physical clocks. Without physical clocks one can’t
differentiate between a crashed process and a paused process.

The physical clocks have to be synchronized to be accurate which means
their values have to be adjusted regularly. To order a set of events,
there is no need to synchronize the system clocks with external time
server because all what we need is to make the values of the clocks be
as close to each other as possible. The algorithm used here to the
clocks synchronized is similar to other related algorithms. The
algorithm mainly depends on sending messages from each node to the
others time-stamped with its local clock. Upon receiving such message,
a client adjusts its clock a new value if it detects that its clock
has drifted from the sender’s clock. The shortcomings of Lamport’s
physical clocks are as follows. (1) A client can’t be figured the
communication delay since incurred when receiving a time update
message because this client does not request the time using a separate
message. Other methods like Cristian’s method measures the
communication delay to be half the round trip delay. So the client
sets its time to the maximum of its local time and the summation of
the other client’s time and the minimum communication delay. In case
of busy network this minimum communication delay is really a small
value. (2) This method assumes an upper bound for the communication
delay. (3) It depends on the discrete clock ticks being frequent
enough to make clock function differentiable at any time. (4) It
assumes also that clocks are never set backward and hence this
algorithm does not deal with such problem. Other algorithms consider
the non-monotonic clocks failed ones and moreover they deal with the
failed clocks gracefully.