"Time is fundamental to our way of thinking," says Leslie Lamport, principal researcher at Microsoft Research and winner of the 2013 Turing Award. And our understanding of time is derived from the more basic concept of the order in which events occur. "The concept of temporal ordering of events pervades our thinking about systems."

This way of thinking also affects our understanding of causality – the relationship between cause and effect. Intuitively we take it that for event A to affect an event B, then event A must have happened before event B in time. This seems straightforward in our experience of time, the order in which events occur seems to be unambiguous in our lives, and we could write a clear timeline of those events.

But as we've seen in the last article, it is possible to have a system, in that instance a distributed program, where the events are only partially ordered in terms of time: there are some events in the system where it is not possible to say which event happened before the other.

Computer science meets special relativity

To illustrate this idea in his paper Time, clocks, and the ordering of events in a distributed system (one of the most influential papers in computer science), Lamport uses spacetime diagrams. These diagrams illustrate distributed systems where the work is split up amongst many different processes, each of which executes its own program, or series of events, and which exchange messages. The horizontal direction represents space, different locations for different processes. And the vertical direction represents time – time moves up the page, later times being higher than earlier times. In these diagrams, dots denote events, vertical lines are the processes, and wavy lines denote the messages.

A spacetime diagram of a distributed system made up of three processes P, Q and R

This diagram may seem familiar if you've ever encountered the area of special relativity. This is because the definition Lamport uses for "happened before" in understanding the flow of events in distributed systems is analogous to that used in Einstein's special theory of relativity.

In computer science an event $a$ in a distributed system is defined to have "happened before" and event $b$, written $a \rightarrow b$, if one can go from $a$ to $b$ in the spacetime diagram by moving forward in time (that is, moving up the page) along process and message lines. For example in the diagram above we can see that $p_1 \rightarrow r_4$. This is analogous to the ordering of events in special relativity. "In relativity the order of events is defined in terms of messages sent," says Lamport.

One of the key concepts in special relativity is that time is relative – two observers of the same event might perceive it to have occurred at different times, depending on their relative motion. (You can read more in What's so special about special relativity.) So if time is relative, if it is personal for each observer, how do you decide when things have happened? How do your order the events in the Universe? The answer, as Lamport noted, is you order events in terms of messages that could be sent between them. In special relativity these messages are equivalent to flashes of light.

(Image by K. Aainsqatsi CC BY-SA 3.0)

Ordering by light

To understand this we're going to imagine ourselves observing a particular event, A, at our location in spacetime (we're the observer, as labelled in the picture to the right). To make it easier to visualise we're going to pretend spacetime is three-dimensional, with two dimensions of space and one dimension for time. So an event is just a point on a flat plane, the plane representing a slice through spacetime at a particular time (the present in the image).

Then imagine a flash of light emanating from that event. The flash would travel at the speed of light, in all directions, creating a circle expanding in size as time moves forward. This creates what is called the future light cone of the event A. This cone contains all the events that could be influenced by the event A, in that they could receive a signal from event A (any such signal travelling at most at the speed of light).

Similarly, the past light cone is defined as all those events in spacetime that could send a signal, travelling at, at most, the speed of light, that could reach event A. So the future and past, in special relativity, which events "happened before" others, are defined in terms of signals moving at the speed of light.

This means that it is possible to have two events in spacetime that both lie outside the future light cone of the other (called space-like separated). In our diagram, for example, any other event located on the plane of the present would be outside of the light cone of our event A, and event A would be outside the light cone of that event. This means that spacetime is, too, only partially ordered by the relation "happened before". There are pairs of events for which you cannot say which happened first.

Violating causality

Causality in both special relativity and computer science is defined in terms of sending messages. In special relativity an event A can influence an event B if it is possible for a flash of light sent from A to reach B (putting B inside the future light cone of A). In a similar way, you can view the definition of "happened before" in a distributed system (such as that illustrated by the spacetime diagram above) in terms of causality: $a \rightarrow b$ means that it is possible for event $a$ to causally effect event $b$.

In 1975 Lamport came across a paper by Bob Thomas and Paul Johnson on distributing a database, where pieces of the database are being stored on different computers which are communicating via messages. Lamport's understanding of special relativity helped him realise that Thomas and Johnson didn't get it quite right. The way they had described their system meant that a "violation of causality was possible." Two events, which Thomas and Johnson had assumed to be executed in one order (say operation A being executed before operation B), actually happened in the opposite order (B $\rightarrow$ A) in terms of the partial ordering of the distributed system (defined in terms of sent messages).

"What was going on was very obvious to me because I had a fairly visceral understanding of special relativity," says Lamport. "The thing about special relativity is that events, which are points in space and time, are not totally ordered; there's a partial order defined by the speed of light."

"I realised that was what was going on this this distributed system [in Thomas and Johnson's paper], and clearly in distributed systems everywhere. You had a completely analogous partial order of the events that happened in a distributed system."

Lamport realised what was needed was a way to totally order the events in a distributed system. And, as you'll see in the next article, all he needed, logically, was time.

About this article

This article is part of our Stuff happens: the physics of events project, run in collaboration with FQXi. Click here to see more articles and videos about the role of events, special relativity and logical clocks in distributed computing.

Rachel Thomas is Editor of Plus. She interviewed Leslie Lamport in September 2016 at the Heidelberg Laureate Forum.