I misunderstood linearizability: a mistake that led me to independently discover the SOSP 2024 Best Paper insight

For context, SOSP (Symposium on Operating Systems Principles) is an A* (meaning top-tier and highly prestigious) academic conference focused on computer systems software and operating systems.

So a month ago, I was trying to understand why Google Spanner uses the term external consistency instead of simply saying linearizability. Because the way the paper described it, they both sounded exactly the same.

After lot of googling and back-and-forth with LLMs and I still wasn't convinced, like I could not explain the difference between the two on paper. I thought if [authors at] Google considered them to be different, maybe my mental model for linearizability had some flaw. So I went back to the definition. It sounded simple:

A strong consistency model guaranteeing that every operation appears to take effect instantaneously at a specific point in time between its invocation and completion, such that a linear ordering can be established that respects real-time ordering of operations.

I kept reading it again and again, used LLMs to dive into the why/how of it, but it still felt like things weren't adding up. It sounded exactly the same as external consistency, so why was Google even making that claim?

For the next few hours, I kept drawing diagrams on a piece of paper trying to come up with scenarios that could maybe help me understand the concept. I even skimmed the whitepaper (Linearizability: A Correctness Condition for Concurrent Objects). I also read this super dope blog by Anish, creator of Porcupine by the way.

And after enough back and forth, accompanied by some amount of banging my head on the wall, it finally made sense. But that clicking of the concept also led me to a goldmine.

To keep things short, linearizability is a per-object correctness property mainly used in the distributed systems ecosystem. External consistency applies the same real-time ordering idea to transactions that may span multiple objects. In the database ecosystem, external consistency IS ESSENTIALLY THE SAME AS strict serializability. So technically we're discussing linearizability v/s strict serializability which makes it much easier to understand now.

But anyway that's not the actual juicy part. Look at the definition of linearizability again:

A strong consistency model guaranteeing that every operation appears to take effect instantaneously at a specific point in time between its invocation and completion, such that a linear ordering can be established that respects real-time ordering of operations.

Do you get it? No? Do you see how the definition is attempting to be a little loose around its guarantees? What do you mean by "appears" and "respects"? It's a definition for the strictest consistency model in the paradigm of distributed systems and the definition uses words like these?

There is a subtle difference between following a rule and respecting a rule. That difference is what led me to independently discover the SOSP 2024 Best Paper insight.

The paper is LazyLog: A New Shared Log Abstraction for Low-Latency Application. At the time of my own mini-discovery, I wasn't even aware the paper existed.

Imagine a distributed system receives two writes concurrently, followed by a read later as per wall-clock time:

A: write(x, 1) @ T=0
B: write(x, 2) @ T=1
C: read(x) @ T=10

And that the writes need to be globally ordered respecting linearizability meaning acquire a position of their own in the globally ordered log.

A traditional design of the system would try to establish an order as soon as the writes come in:

“Okay, A happened before B, I get it. Let's assign them positions one by one in that order now.
The clients need to wait until then.”

But think about this: if a linearizable system only has to respect the real-time ordering that means we never need to establish an order upfront on writes. Right? Right. As long as we respect the order in which they came in, we're still obeying the rules of linearizability.

So now, what if the system accepted both writes, stored these writes durably somewhere, ack'ed back to the client and waited 40 seconds before deciding their final order? Would it still be linearizable?

YES. A HARD YES.

Because again, as long as the final history observed by clients can be explained as a valid timeline that respects what actually happened, the system is still linearizable. The system does not need to know the final ordering immediately (or in the words of the paper, eagerly). It only needs to produce a valid ordering when the history becomes visible.

“Okay, A happened before B, I get it. I'll ack back to the client right now. And then look into 
how I could assign these writes a position in the globally shared order. Once that's done, I'll 
have respected linearizability because my assigned ordering still respects the real-time 
ordering in which they came in.”

So naturally I thought, "Surely someone has already built something around this idea." After all, I have only been studying distributed systems for a few months now. Researchers with decades of experience had probably explored this entire space to the utmost depth. So I was happy with what I came up with and moved forward.

A week ago, I was browsing papers from SOSP '23/'24/'25 just to find something that could interest me. One paper from 2024 caught my attention. And for absolutely no reason other than the fact that its name sounded cool: LazyLog.

I downloaded it and read the abstract. And my jaw literally hit the floor. This was the exact idea, not the implementation details nor the complete system design, but the actual core intuition.