Assigning Lamport & Vector Timestamps

Introduction

This is a brief example of assigning Lamport Timestamps and Vector Timestamps. The details of the algorithms are described in the Clock Synchronization notes. This page is less formal and supplements the lecture notes.

Lamport Clocks

Each process maintains a single Lamport timestamp counter. Each event on the process is tagged with a timestamp from this counter. The counter is incremented before the event timestamp is assigned. If a process has four events, a, b, c, d, they would get Lamport timestamps of 1, 2, 3, 4.

If an event is the sending of a message then the timestamp is sent along with the message. If an event is the receipt of a message then the the algorithm instructs you to compare the current value of the process' timestamp counter (which was just incremented before this event) with the timestamp in the received message. If the timestamp of the received message is greater than that of the current system, the system timestamp is updated with that of the timestamp in the received message plus one. This ensures that the timestamp of the received event and all further timestamps will be greater than that of the timestamp of sending the message as well as all previous messages.

In the figure below, event k in process P1 is the receipt of the message sent by event g in P0. If event k was just a normal local event, the P1 would assign it a timestamp of 4. However, since the received timestamp is 6, which is greater than 4, the timestamp counter is set to 6+1, or 7. Event k gets the timestamp of 7. A local event after k would get a timestamp of 8.

With Lamport timestamps, we're assured that two causally-related events will have timestamps that reflect the order of events. For example, event c happened before event k in the Lamport causal sense: the chain of causal events is c→d, d→f, f→g, and g→k. Since the happened-before relationship is transitive, we know that c→k (c happened before k). The Lamport timestamps reflect this. The timestamp for c (3) is less than the timestamp for k (7). However, just by looking at timestamps we cannot conclude that there is a causal happened-before relation. For instance, because the timestamp for l (1) is less than the timestamp for j (3) does not mean that l happened before j. Those events happen to be concurrent but we cannot discern that by looking at Lamport timestamps. We need need to employ a different technique to be able to make that determination. That technique is the use of vector timestamps.

lamport clocks

Lamport Clock Assignments


Vector Clocks

With vector clocks, we assume that we know the number of processes in the group. Our timestamp is now a vector of numbers, with each element corresponding to a process. Each process knows its position in the vector. For example, in the example below, the vector corresponds to the processes (P0, P1, P2).

As with Lamport's algorithm, the element corresponding to the processor in the vector timestamp is incremented prior to attaching a timestamp to an event. If a process P0 has four events, a, b, c, d, they would get Vector timestamps of (1,0,0), (2, 0, 0), (3, 0, 0), (4, 0, 0). If a process P2 has four events, a, b, c, d, they would get Vector timestamps of (0,0,1), (0, 0, 2), (0, 0, 3), (0, 0, 4).

The entire vector is sent along with a message. When the message is received by a process (that is an event that will get a timestamp), the reciving process does the following:

  1. increment the counter for the process' position in the vector, just as it would prior to timstamping any local event.

  2. Peform an element-by-element comparison of the received vector with the process' timestamp vector. Set the process' timestamp vector to the higher of the values:

    for (i=0; i < num_elements; i++) if (received[i] > system[i]) system[i] = received[i];

To determine if two events are concurrent, do an element-by-element comparison of the corresponding timestamps. If each element of timestamp V is less than or equal to the corresponding element of timestamp W then V causally precedes W and the events are not concurrent. If each element of timestamp V is greater than or equal to the corresponding element of timestamp W then W causally precedes V and the events are not concurrent. If, on the other hand, neither of those conditions apply and some elements in V are greater than while others are less than the corresponding element in W then the events are concurrent. We can summarize it with the pseudocode:

isconcurrent(int v[], int w[]) { bool greater=false, less=false; for (i=0; i < num_elements; i++) if (v[i] > w[i]) greater = true; else (v[i] < w[i]) less = true; if (greater && less) return true; /* the vectors are concurrent */ else return false; /* the vectors are not concurrent */ }

In the figure below, the timestamp for m is less than the timestamp for g because each element in m is less than or equal to the corresponding element in g. That is, 0 ≤ 6, 0 ≤ 1, and 2 ≤ 2.

The timestamps for c and j, on the other hand, are concurrent. If we compare the first element, we see that c ≥ j (3 ≥ 2). If we compare the second element, we see that c ≤ j (1 ≤ 2). Because of this, we cannot say that the vector for c is either less than or greater than the vector for j.

vector clocks

Vector Clock Assignments