Logical Clocks¶

Important

Lamport and Vector Clocks have no relation to a physical clock. They cannot be associated with wall time.

Vector Clocks and their simpler relative Lamport Clocks help us understand order across multiple streams and processes. These can be used to construct reliable distributed systems without Aeron Cluster.

Lamport Clocks¶

Back in the late 1970's Leslie Lamport wrote a paper in which he introduced logical clocks. The paper had three main points: firstly, if a distributed system is built up of multiple independent servers, and some of the servers never interact with each other, then there is little theotical need for the non-interacting server clocks to be sychronised since any difference would never be observed. Secondly, in distributed systems, he showed that time is less important than agreement across components of the order of events in which things occur. And finally, he provided algorithms for partial causal ordering and an extension which provides total ordering.

Lamport clocks are event counters that are incremented with every interaction. They are incremented and sent as a part of a message by a sending process and are in turn incremented by a receiving process before it sends it on to the business logic. The value produced by a Lamport clock is a Lamport timestamp.

A Lamport clock offers us a single guarantee – if we have two timestamp values a and b, and when comparing them we see that a < b, then we can guarantee that the clock value of a was smaller than the clock value of b. When different processes have a < b, it means that they all agree that a happened before b.

Adding a Lamport timestamp on the sending side can be done by:

long time = 0;
...
void send(byte[] message)
{
    time = time + 1;
    send(message, time);
}

And on the receiving side it is:

long time = 0;
...
void receive(byte[] message, long timeStamp)
{
    time = max(timeStamp, time) + 1;
    //do stuff with message and new time
    process(message, time);
}

Visually, the behavior of Lamport Clocks is as follows:

The above example illustrates how Lamport Clocks can give ordering to the causal event flows Event C -> Event D and Event A -> Event B -> Event E within the process space of Process A. Note that we cannot say anything about Event A causing Event C. It also shows how Lamport Clocks may result in duplicate clock values across processes, and how clock values cannot be taken to be reliable representation of the real-world happened before.

See theory project namespace com.aeroncookbook.lamport for a simplistic example.

Lamport Clocks can be extended to provide total ordering with multiple processes. In this case, you will need to introduce a tie breaker value such as a derived process identifier, and have each process hold two values - the Lamport timestamp value (timestamp) and process identifier (id). The process identifier could be constructed from a process specific value such as an IP address. If we consider two processes, m and n: (m.Timestamp, m) < (n.Timestamp, n) then we have total ordering if and only if m.Timestamp<n.Timestamp or (m.Timestamp=n.Timestamp and m<n). Note this does not necessarily relate to actual event ordering.

Lamport clocks cannot tell us if a message was concurrent, and cannot be used to infer causality between events. Vector clocks are a more sophisticated variant which gives us more guarantees, including knowledge of concurrency & causal history.

Vector Clocks¶

Vector Clocks extend the capabilities of Lamport Clocks to allow us to understand the ordering across multiple processes which cross communicate. They can also be invaluable in understanding the flow of messages in a distributed system.

As a data level, Vector clocks are vectors of event counters. The vectors are stored in positionally consistent offsets within the vectors - each node in the system occupies a fixed position within the vector. If we take a system with N nodes, then the clock would be something like [c₁,c₂,c₃,...,c_N]. For example, the clock at the 2^nd node:

the clock value at c₂ is the local logical clock of the node
the entire clock of [c₁,c₂,c₃,c_N] forms the global logical clock of the node

The logic is similar to that of Lamport Clocks:

long[] clocks = new long[NODE_COUNT];
int nodeOffset = 2;

...

void updateLocalClock()
{
    clocks[nodeOffset] = clocks[nodeOffset] + 1;
}

...

void send(byte[] message)
{
    updateLocalClock();
    send(message, clocks);
}

...

void receive(byte[] message, long sendingNode, long[] inputClock)
{
    updateLocalClock();

    for (int i = 0; i < NODE_COUNT; i++)
    {
        if (i != nodeOffset)
        {
            clocks[i] = max(clocks[i], inputClock[i]);
        }
    }

    //do stuff with message and new time
    process(message, clocks);
}

Key aspects of the code:

Line 9, which updates the local clock within the vector
Line 15 and 23, which update the clock before sending/receiving the data (note any local actions done should also increase the clock)
Lines 25-31, which brings any larger clock values from the received clock vector into the local clocks vector (excluding itself).

This logic provides a strong clock that can be used across processes to define order. The vectors can be used to compare timestamps as follows:

If clock C₁ has smaller or equal values in all entries compared to clock C₂, and at least one entry in C₁ is smaller than the equivalent entry in clock C₂, then the time in clock C₁ is before clock C₂.

This comparison can in turn be used for understanding if two messages are causally related or concurrent.