Time Clock by Lamport

Summary

This paper explained how time clock works in distributed systems. Logical clock concept is explained in this paper. This really helps me understand the concept. (I guess this is the origin of logic clock concept)

The paper first defined events of a process form a sequence and a occurs before b in this sequence if a happens before b. Happens before relationship is denoted by "->" symbol.

The "->" relation satisfying the following 3 conditions:

(1) if a and b are events in the same process, and a comes before b, then a -> b
(2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a -> b
(3) if a->b and b -> c then a -> c. Two distinct events a and b are said to be concurrent if a not-> b and b not-> a

Space-time diagram is helpful for visualizing the relationship.

Logical Clocks

-> An abstract point of view in which a clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred.

This also applies to our real world physical clocks (assign number to an event, or continues increasing number for reference of "happens before" relationship)

A function is used in each process to assign number C<a> to any event a in that process.
so for any events a, b:
if a -> b then C(a) < C(b) because logical clock is just assigning number to each event and with increasing number for "happens before" relationship
In terms of a space-time diagram. we imagine that a process clock "ticks" (increased) through every number. With ticks occurring between the process events. For example, if a and b are consecutive events in process Pi with Ci(a) = 4 and Ci(b) = 7, then clock ticks 5, 6 we can draw a dashed line to represent it as shown below

image.png

we can consider the tick lines to be the time coordinate lines of some Cartesian coordinate system on space-time.

y axis is the number represent time (increasing)

The reader may find it helpful to visualize a two-dimensional spatial network of processes, which yields a three-dimensional space-time diagram.

Really helpful for visualizing!

IR1 Each process Pi increments Ci between any two successive events (time is continuously increasing)

IR2 If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm

"=>" defines the total ordering where a => b if and only if either (i) Ci(a). < Cj(b) or (ii) Ci(a) = Cj(b) and Pi < Pj

The reason for implementing a correct system of logical clocks is to obtain a total ordering.

Since collection of processes which share a single resource, only one process can use the resource at a time, so the processes must synchronize themselves to avoid conflict. An algorithm for granting the resource to a process which satisfies the following 3 conditions:

1. A process which has been granted the resource must release it before it can be granted to another process.
2. Different requests for the resource must be granted in the order in which they are made.
3. If every process which is granted the resource eventually releases it, then every request is eventually granted.

We will use IR1 and IR2 to define a total ordering => of all events.

Each process maintains its own request queue which is never seen by any other process. We assume that the request queues initially contain the single message T0:P0 request resource, where P0 is the process initially granted the resource and T0 is less than the initial value of any clock. (sentinel node?)

5 rules of the Algorithm

1. to request the resource, process Pi sends the message Tm:Pi requests resource to every other process, and puts that message on its request queue, where Tm is the timestamp of the message.
2. When process Pj receives the message Tm:Pi requests resource, it place it on its request queue and sends a (timestamped) acknowledgment message to Pi.
3. To release the resource, process Pi removes any Tm:Pi requests resource message from its request queue and sends a (timestamped) Pi releases resource message to every other process.
4. When process Pj receives a Pi release resource message, it removes any Tm:Pi requests resource message from its request queue.
5. Process Pi is granted the resource when the following two conditions are satisfied (i) There is a Tm:Pi requests resource message in its request queue which is ordered before any other request in its queue by the relation =>. (ii) Pi has received a message from every other process time-stamped later than Tm.

[reference]
https://lamport.azurewebsites.net/pubs/time-clocks.pdf