Lamport Clocks

Assuming that we cannot achieve accurate clock synchronization - or starting with the goal that our system should not be sensitive to issues with time synchronization, how can we order things?

Lamport clocks and vector clocks are replacements for physical clocks which rely on counters and communication to determine the order of events across a distributed system. These clocks provide a counter that is comparable across different nodes.

A Lamport clock?is simple. Each process maintains a counter using the following rules:

• Whenever a process does work, increment the counter
• Whenever a process sends a message, include the counter
• When a message is received, set the counter to?max(local_counter, received_counter) + 1

Expressed as code:

function LamportClock() {
  this.value = 1;
}

LamportClock.prototype.get = function() {
  return this.value;
}

LamportClock.prototype.increment = function() {
  this.value++;
}

LamportClock.prototype.merge = function(other) {
  this.value = Math.max(this.value, other.value) + 1;
}        

A?Lamport clock?allows counters to be compared across systems, with a caveat: Lamport clocks define a partial order. If?timestamp(a) < timestamp(b):

• a?may have happened before?b?or
• a?may be incomparable with?b

This is known as clock consistency condition: if one event comes before another, then that event's logical clock comes before the others. If?a?and?b?are from the same causal history, e.g. either both timestamp values were produced on the same process; or?b?is a response to the message sent in?a?then we know that?a?happened before?b.

Intuitively, this is because a Lamport clock can only carry information about one timeline / history; hence, comparing Lamport timestamps from systems that never communicate with each other may cause concurrent events to appear to be ordered when they are not.

Imagine a system that after an initial period divides into two independent subsystems which never communicate with each other.

For all events in each independent system, if a happened before b, then?ts(a) < ts(b); but if you take two events from the different independent systems (e.g. events that are not causally related) then you cannot say anything meaningful about their relative order. While each part of the system has assigned timestamps to events, those timestamps have no relation to each other. Two events may appear to be ordered even though they are unrelated.

However - and this is still a useful property - from the perspective of a single machine, any message sent with?ts(a)?will receive a response with?ts(b)?which is?> ts(a).

I hope you found the article useful.

Happy Coding :)