What is the happened-before relation?

We’re used to thinking of time as a total order: given two events, one happened before the other. At my desk, I sit down before I turn on my computer. All the things happening to you have a total order, because you’re a timeline. Sitting down at my desk and turning on my computer happened at the same place (my desk). Because of this, they have a total order. This total order is nicely tracked by the clock on my desk. If you compared the reading of that clock at both events, you would find that the time at which I sat at my desk was less than the time I turned on my computer.

But once we look at “distributed systems”, where events can happen in multiple places, it gets weird. Do I sit down at my desk before Eve sits down at hers in New York? It seems hard to tell. Distributed systems literature says it’s not necessarily the case that one happened before the other. It’s not just that it’s hard to tell whether I sat down before Eve: the events can happen “concurrently”, or “at the same time”.

What does “concurrent” mean? It does not mean that “the clock on my wall read the same as the clock on the New York office wall”. “Time” in distributed systems is not about wall clocks!

Instead, “time” in distributed systems is all about causality. Let’s say I sit down, then phone Eve; and Eve only sits down after I call her. We then know that I sat down first, because I caused Eve to sit down (if you squint). Typically, cause-and-effect is modelled as “message-passing”. If I send Eve a message, then my sending the message causes Eve to receive the message. In the “distributed systems” definition, Jim calling Eve “happened before” Eve picking up.

So we have two ways to determine whether A happened before B:

A and B happened at the same place, and the wall clock says A happened before B.
A was a “send message”, and B was the corresponding “receive message”.

Let’s apply this to our example, where we have four events:

A: Jim sits down.
B: Jim calls Eve.
C: Eve picks up.
D: Eve sits down.

Because A and B happened in the same place (Jim’s desk), we can use Rule 1 to say that A happened before B. Because B was a “send message” and C was a “receive message”, we can use Rule 2 to say that B happened before C. Because C and D happened in the same place (Eve’s desk), we can use Rule 1 again to say that C happened before D.

So, A happened before D! Well, actually, we need one more rule for this:

(Transitivity) If A happened before B, and B happened before C, then A happened before C.

We now have all the pieces of the “happened-before relation” (as originally defined by Leslie Lamport). This relation is supposed to capture our sense of time, or our sense of causality, and basically asserts that time and causality are the same things.

To visualize such events in “time”, we usually draw diagrams like this:

message-passing processes

Here, P, Q and R are “processes”. In our example, “Jim’s desk” and “Eve’s desk” are processes: things fixed in position. The arrows are messages being passed between processes. In our example, Jim calling Eve would be modelled as a message.

It’s important to understand that these “processes” and “messages” are really not specific to computing! The happened-before relation is more a model of physics. Computers, being part of the same world, are of course subject to the same rules.

Tagged #concurrency, #programming, #computer-science.

More by Jim

What does the dot do in JavaScript?

foo.bar, foo.bar(), or foo.bar = baz - what do they mean? A deep dive into prototypical inheritance and getters/setters. 2020-11-01

Smear phishing: a new Android vulnerability

Trick Android to display an SMS as coming from any contact. Convincing phishing vuln, but still unpatched. 2020-08-06

A probabilistic pub quiz for nerds

A “true or false” quiz where you respond with your confidence level, and the optimal strategy is to report your true belief. 2020-04-26

Time is running out to catch COVID-19

Simulation shows it’s rational to deliberately infect yourself with COVID-19 early on to get treatment, but after healthcare capacity is exceeded, it’s better to avoid infection. Includes interactive parameters and visualizations. 2020-03-14

The inception bar: a new phishing method

A new phishing technique that displays a fake URL bar in Chrome for mobile. A key innovation is the “scroll jail” that traps the user in a fake browser. 2019-04-27

The hacker hype cycle

I got started with simple web development, but because enamored with increasingly esoteric programming concepts, leading to a “trough of hipster technologies” before returning to more productive work. 2019-03-23

Project C-43: the lost origins of asymmetric crypto

Bob invents asymmetric cryptography by playing loud white noise to obscure Alice’s message, which he can cancel out but an eavesdropper cannot. This idea, published in 1944 by Walter Koenig Jr., is the forgotten origin of asymmetric crypto. 2019-02-16

How Hacker News stays interesting

Hacker News buried my post on conspiracy theories in my family due to overheated discussion, not censorship. Moderation keeps the site focused on interesting technical content. 2019-01-26

My parents are Flat-Earthers

For decades, my parents have been working up to Flat-Earther beliefs. From Egyptology to Jehovah’s Witnesses to theories that human built the Moon billions of years in the future. Surprisingly, it doesn’t affect their successful lives very much. For me, it’s a fun family pastime. 2019-01-20

The dots do matter: how to scam a Gmail user

Gmail’s “dots don’t matter” feature lets scammers create an account on, say, Netflix, with your email address but different dots. Results in convincing phishing emails. 2018-04-07

The sorry state of OpenSSL usability

OpenSSL’s inadequate documentation, confusing key formats, and deprecated interfaces make it difficult to use, despite its importance. 2017-12-02

I hate telephones

I hate telephones. Some rational reasons: lack of authentication, no spam filtering, forced synchronous communication. But also just a visceral fear. 2017-11-08

The Three Ts of Time, Thought and Typing: measuring cost on the web

Businesses often tout “free” services, but the real costs come in terms of time, thought, and typing required from users. Reducing these “Three Ts” is key to improving sign-up flows and increasing conversions. 2017-10-26

Granddad died today

Granddad died. The unspoken practice of death-by-dehydration in the NHS. The Liverpool Care Pathway. Assisted dying in the UK. The importance of planning in end-of-life care. 2017-05-19

How do I call a program in C, setting up standard pipes?

A C function to create a new process, set up its standard input/output/error pipes, and return a struct containing the process ID and pipe file descriptors. 2017-02-17

Your syntax highlighter is wrong

Syntax highlighters make value judgments about code. Most highlighters judge that comments are cruft, and try to hide them. Most diff viewers judge that code deletions are bad. 2014-05-11

Want to build a fantastic product using LLMs? I work at Granola where we're building the future IDE for knowledge work. Come and work with us! Read more or get in touch!

This page copyright James Fisher 2017. Content is not associated with my employer. Found an error? Edit this page.

What is the happened-before relation?

Similar posts

More by Jim