Logical Time and Lamport Clocks (Part 1)
Tags: distributedsystems, beginners, computerscience
Published: 2019-11-20 16:19:01

---
title: Logical Time and Lamport Clocks (Part 1)
published: true
date: 2019-11-14 16:34:19 UTC
tags: distributedsystems, beginners, computerscience
canonical_url: https://medium.com/baseds/logical-time-and-lamport-clocks-part-1-d0317e407112
cover_image: https://p78.f0.n0.cdn.getcloudapp.com/items/6quDgovy/Image+2019-11-20+at+11.13.07+AM.png?v=9e719a9a3719ce99083acad8ed9f0c6d
description: Our reason for wanting to know the order of some events in a system all stems back to the same desire: we care about ordering events so we can determine how those events are connected.
series: baseds
---

Over the course of this series, we’ve seen many instances of how things can be more complicated than they seem. We saw this with [failure](https://dev.to/vaidehijoshi/modes-of-failure-part-1-4db1), and we saw it with [replication](https://dev.to/vaidehijoshi/redundancy-and-replication-duplicating-in-a-distributed-system-p73). More recently, we discovered that even the [concept of time](https://dev.to/vaidehijoshi/ticking-clocks-in-a-distributed-system-b41) is more complex that we might have originally thought.

However, when the things that you thought you knew seem more convoluted than ever, sometimes the answer is to keep it simple. In other words, we can keep a problem simple by stripping out the confusing parts and trimming it down to its most essential parts. In fact, this approach is exactly what one computer scientist did in the late 70’s when he was, just like us, trying to figure out how to make sense of time in a distributed system.

The previous two posts on [clocks](https://dev.to/vaidehijoshi/ticking-clocks-in-a-distributed-system-b41) and the [ordering of event](https://dev.to/vaidehijoshi/ordering-distributed-events-2o7b)s in a distributed system have both been building up to the topic we’re finally ready to uncover: logical time and Lamport clocks! There’s a lot to cover, so we’ll spread it out between two posts. Let’s dive right into part one!

### Causality and “happens before”

The story of logical clocks starts in 1978, when a paper was published in the _Communications of ACM_ journal that would go down in history. [Leslie Lamport](http://www.lamport.org/), a computer scientist at Massachusetts Computer Associates, wrote about his research around ordering events in a distributed system. This paper, entitled [“Time, Clocks, and the Ordering of Events in a Distributed System”](https://lamport.azurewebsites.net/pubs/time-clocks.pdf), would go on to be one of the most-cited papers in computer science, and would also win the Principles of Distributed Computing Influential Paper Award more than [20 years later](http://www.podc.org/influential/2000-influential-paper).

![](https://cdn-images-1.medium.com/max/1024/1*B5-RflcB3mx-p_3472yMIA.jpeg)<figcaption>Lamport’s paper on causal ordering was published in 1978!</figcaption>

In the paper, Lamport outlines how we think about time as humans, and why we need to shift our paradigm when it comes to distributed systems, and the idea of [partial ordering](https://dev.to/vaidehijoshi/ordering-distributed-events-2o7b). He explains that, “In a distributed system, it is sometimes impossible to say that one of two events occurred first”.

![](https://cdn-images-1.medium.com/max/1024/1*_5OCO_U9wWZ1H0F4acPYyQ.jpeg)<figcaption>Why do we care about ordering events? So that we can track causality!</figcaption>

As Lamport cites in his paper, the reason that we care about time is so that we can figure out the order in which things happen. While this is certainly harder (or sometimes impossible!) to do in a distributed system, our reason for wanting to _know_ the order of some events in a system all stems back to the same desire: we care about ordering events so we can determine how those events are connected. When dealing with events in _any_ system, the reason we actually want to order them is so that we can see the chain of events within the system. Within a distributed system in particular, we this means that we are often trying to determine if an event at one node affects or causes an event at another node.

But, as we’ve seen in our own study of distributed systems, this task is no easy feat. When a system is distributed, there is [no global clock](https://dev.to/vaidehijoshi/ticking-clocks-in-a-distributed-system-b41), which means that we cannot depend on any central time source. This also means that the events in our system are not [totally ordered](https://dev.to/vaidehijoshi/ordering-distributed-events-2o7b), which means we can’t be sure of exactly _when_ every event in the system took place. Lamport’s paper acknowledges all of these constrains and empathizes with how tricky this problem really is!

Lamport’s solution is to shift our thinking. He presents a novel idea: we don’t actually need to think about causality in the context of total ordering to start. Instead, he says that we can start with a partial ordering of events, and then just deal with figuring out which events happened before other events. Once we figure out a partial ordering, we can turn it into a consistent total ordering.

![](https://cdn-images-1.medium.com/max/1024/1*_PdU1sv7gRJnExmFEo3KhA.jpeg)<figcaption>Lamport’s logical clocks allow us to shift from happened “when” to happened “before”.</figcaption>

So how do we do this? Well, to start, we need to shift from thinking about _when_ an event happened to what the event happened _before_.

### Shifting from “when” to “before”

The idea of one event happening before another is central to Lamport’s paper. He uses the **→** shorthand notation to indicate the **_happens before_** relationship, or the fact that one event happened before another. For example, if we know that one event, _a_, happened before another event, _b_, then we can say that _a_ → _b_, or _a_ happened before _b_.

The happens before relationship can also be applied transitively. In other words, we can create a chain of events where one event happened before another. If we say that _a_ → _b_ and _b → c_, then by using the transitive property, we can say that _a → c_, or _a_ happened before _c._ As we might be able to imagine, we could very easily string together a chain of events, where one event happens before another, which happens before another, and so on and so forth.

![](https://cdn-images-1.medium.com/max/1024/1*jBl56kdG5zmTewcyt1J6Vg.jpeg)<figcaption>Understanding the “happened before” notation.</figcaption>

But wait a second — we keep talking about different events in the system, but we haven’t really clarified what an event could possibly be! As it turns out, an event in a distributed system can take different forms. As we know, there can be many [different nodes](https://dev.to/vaidehijoshi/many-nodes-one-distributed-system-kl9) in a distributed system. Each node has its own local system clock, and it is capable of processing its own tasks. However, the nodes can also communicate between one another, sending messages back and forth.

An **_event_** encompasses all of the different things that can happen within and between nodes in a system. An event could be something that occurs on a single process or node. An event also includes any **_send events_** , where a node sends a message to another node or process. Conversely, we must also consider **_receive events_** , when a node receives an incoming message from elsewhere in the system.

In the example above, we can see examples of all three of these events. We have two processes, P and Q. There is one event, Q3, which occurs on process Q that are not related to sending or receiving any messages. This is our basic event that indicates that something occurred on the node for process Q. However, we also have a few send events: P1, Q1, Q4. These are all events that indicate that we are sending messages out from a node to somewhere else in the system. On the other hand, P2, P3, and Q2 are each receive events, which indicate that we have received some message from another node in the system.

Now that we understand what an event in a system could be, we can turn back to the happens before relationship. When we say that an event _a_ _→_ _b_, we are asserting that event _a_ occurred before _b_, because _a_ happened before _b_. We can say that these two events are **_causally ordered_** , where the ordering of the events is contingent upon one event causing another to happen.

![](https://cdn-images-1.medium.com/max/1024/1*RpmP-aPCiqMfvrGB81puJg.jpeg)<figcaption>Causally-ordered and concurrent events across two processes.</figcaption>

There are a few rules to causal ordering that are important for us to understand. In order for _a_ _→_ _b_ to be causally ordered, one of the following three situations must be true:

1. Events _a_ and _b_ must occur on the **_same_**  **_process_** , and _a_ must occur before _b_ occurs on the process.
2. The events can occur on **_different_**  **_processes_** so long as _a_ is the send event that corresponds to _b,_ which must be its receive event.
3. The events are **_transitively linked_** with another event in the system, but _a_ still happens before _b_. For example, if _a_ happens before _c_, and _c_ happens before _b_, then we know that _a_ _→ b_.

As messages travel through time and across space from one process to another and, we can start to construct chains of causally events (also called **_causal paths_** ) and see how different events across processes are connected to one another. For example, in processes P and Q, Q1_→_ P3 (through event P2), and P1 _→_ Q4 (through events Q2 and Q3).

Finally, it’s worth mentioning that, if two events _a_ and _b_ do not happen before one another, than we can say that _a ≠> b_ and _b ≠> a_, and that the two events are **_concurrent_**. We will cover this in much more depth in part two of this post, but for now, we should just note that concurrent events do not have causal paths from one to another.

### Logical clocks to the stage

In addition to the idea of “happens before”, another core concept that Lamport introduces in his paper is the logical clock. As we already know, each node or process in a distributed system has its own [concept of time](https://dev.to/vaidehijoshi/ticking-clocks-in-a-distributed-system-b41), or its own local clock. However, Lamport’s take on local clocks is different that what we’ve seen before.

![](https://cdn-images-1.medium.com/max/1024/1*OAmD3WgougNwyj-xexU0dw.jpeg)<figcaption>How do the clocks factor in?</figcaption>

Lamport suggests using something different from the typical physical clock that we all think of. Instead of using each process’s physical clock to track the order of events, we can instead use a **_counter_**. The counter can start with an initial time (like 0), and we can treat that counter as the processes own local clock.

Lamport continues with this idea by proposing that, not only will every process within a distributed system have its own counter clock, but each _event_ that is recorded on a process should also have a **_value_** on that process’s local clock. Furthermore, the value of each of these events on the clock must mirror any happened before relationships. For example, if event _a_ _→ b_, then the clock time for when event _a_ occurred must be less than the clock time for whenever event _b_ occurred; in other words, clock(_a_) < clock(_b_).

By using basic counters instead of physical clocks, Lamport simplifies clocks into something a little easier to deal with. These counter clocks are called logical clocks. A **_logical clock_** is quite different from a physical clock in that there is no central notion of time, and the clock is just a counter that increments based on events in the system.

![](https://cdn-images-1.medium.com/max/1024/1*xn9OpEEOENBcg2KouYDCXQ.jpeg)<figcaption>Logical clocks: a definition.</figcaption>

Each process in a distributed system can use a logical clock to causally order all the events that are relevant to it. As events occur in a process — whether they are send or receive events — the process’s clock counter is incremented by an arbitrary amount. We’ll learn more about how this works in practice in part two of this post. We’ll also be introduced to Lamport’s algorithm for incrementing counters, and how to obey causality across processes. There’s so much interesting stuff to learn; thankfully we have more time and another post to cover it all!

### Resources

Conveniently, Lamport’s work on logical clocks and causal ordering is well-taught and written about. There are a lot of great resources that introduce these topics, with varying complexities. If you’d like to do some further reading, check out some of my favorite resources, which I’ve listed below!

1. [Time, Clocks, and the Ordering of Events in a Distributed System](https://lamport.azurewebsites.net/pubs/time-clocks.pdf), Leslie Lamport
2. [Time, Clocks and Ordering of Events in a Dist. System](https://www.youtube.com/watch?v=hK6m6WBk-d8&t=3s), Dan Rubenstein
3. [Time and Ordering: Lamport Timestamps](https://www.youtube.com/watch?v=CMBjvCzDVkY), Indranil Gupta
4. [Lamport’s Logical Clocks](https://mwhittaker.github.io/blog/lamports_logical_clocks/), Michael Whittaker
5. [Logical Clocks](https://www.cs.rutgers.edu/~pxk/rutgers/notes/content/08-logical-clocks-slides.pdf), Professor Paul Krzyzanowski

* * *