No Effect Before Its Cause: From Einstein to Lamport

Once upon a time, there was a boy named Bob and a girl named Alice. They lived far away from each other and decided to work on a literature assignment together using Notion, a collaborative document tool. As they edited the same document simultaneously, Alice added "is pretty" at the end of a sentence. Just before Alice's edit reached Bob, his internet connection dropped and he didn't notice.

Later, still unaware of her edit, Bob typed "shall I pick it?" in the same spot. When his connection came back, his edit synced first. Now Notion faced a problem: it had to determine what the sentence should say. The obvious rule was "newest timestamp wins," but this led to a lost update, where Bob's edit overwrote Alice's, even though she never saw it.

This issue is a central problem in leaderless replication, where every copy of the data accepts writes independently and no central entity decides the order.

Before computers existed, physicists encountered a similar problem over a century ago. In 1905, Albert Einstein realized that two events can be simultaneous for one person and not simultaneous for another, and both are correct. He used a train analogy to illustrate this concept. If a woman stands exactly halfway between two lightning strikes on a platform, both flashes reach her at the same time, and she says they are simultaneous.

However, if a man is sitting in the middle of the train, the light from the front flash reaches him before the one from the rear, making him believe the front flash happened first. Both perspectives are correct, and there is no master clock to determine the actual order.

This idea of relativity and the relativity of simultaneity forms the basis of leaderless replication, where no central clock determines the order of events. In 1978, Leslie Lamport applied this concept to distributed systems when he wrote his paper "Time, Clocks, and the Ordering of Events in a Distributed System." He compared a network of computers to a distributed universe, where each machine is an observer with its own clock and no master clock to resolve conflicts.

Lamport defined the "happens-before" relationship, which does not rely on clocks but rather on the causal relationship between events. If one event happens before another, it is ordered; if not, they are concurrent. This concept helps programmers solve the problem of lost updates and ensure data consistency in distributed systems.