Leslie Lamport: Why the Smartest People Don't

There's a particular kind of genius that doesn't recognize itself. Leslie Lamport—Turing Award winner, inventor of the Paxos algorithm, author of the most cited paper in distributed systems—spent most of his career thinking he wasn't particularly smart.

"Stupid people think they're smart because they're too stupid to realize they're not," Lamport told Ryan Peterman in a recent interview. Only after winning computing's highest honor did he understand what set him apart: not raw intelligence, but what Edsger Dijkstra called "a remarkable ability at abstraction."

That ability shows up in Lamport's origin story, which begins with hubris and a bug. In 1972, he read a solution to Dijkstra's concurrent programming problem in Communications of the ACM and thought: that shouldn't be so hard. He whipped up what he believed was a simpler algorithm for two processes and submitted it. Two weeks later, the editor wrote back pointing out the bug.

The experience taught Lamport two things. First, that concurrent programs are brutally hard to get right and require mathematical proofs of correctness. Second—and this is pure engineer psychology—that he was going to solve that damn problem.

The Deli Counter That Changed Computing

The solution Lamport developed became the bakery algorithm, inspired by the ticket system at deli counters. When customers arrive, they take a number. The next person served has the lowest unserved number. Simple enough for a deli, trickier when there's no central ticket dispenser and each process has to choose its own number.

But the elegant part wasn't the algorithm itself—it was what Lamport discovered when he wrote the proof of correctness. The prevailing wisdom held that you couldn't implement mutual exclusion (ensuring only one process accesses a shared resource at a time) without some lower-level mutual exclusion primitive. Most solutions assumed atomic operations on shared memory: that reads and writes happened in some definite order, never simultaneously.

Lamport's algorithm didn't need that assumption. Each piece of shared memory was written by only one process. If another process happened to read while a write was occurring and got garbage data—literally any random value—the algorithm still worked.

When he showed the proof to his colleague Anatol Hol, Hol didn't believe it. "I wrote the proof on the whiteboard for him and he couldn't find anything wrong with it, but he went home saying there must be something wrong with it," Lamport recalls. There wasn't.

What Dijkstra Recognized

The month Lamport spent in the Netherlands in 1976, working with Dijkstra's group, produced one published paper. But it revealed something about how innovation actually works—and why Lamport didn't think of himself as smart.

Dijkstra and colleagues had written the first concurrent garbage collection algorithm. Lamport looked at it and saw a simplification: the free list (where unused memory goes) could be part of the regular data structure instead of requiring a special process with its own coordination logic. He sent the suggestion. In the next version of the paper, Dijkstra had made him an author.

"I thought that was very generous of him because it seemed like a very simple idea, a very obvious idea," Lamport says. "I later realized it was not an obvious idea to most people, and that had actually impressed Dijkstra."

What Lamport considered obvious—collapsing a complex coordination problem into a simpler abstraction—was the thing Dijkstra recognized as exceptional. The gift wasn't seeing complexity; it was seeing through it.

When Relativity Meets Distributed Systems

Lamport's most cited paper, "Time, Clocks, and the Ordering of Events in Distributed Systems," emerged from an even simpler observation. Someone sent him a paper on distributed databases, and Lamport noticed their solution would execute operations as if they occurred in sequence, but that sequence might not match the order events actually happened.

The fix came from physics. In special relativity, one event happens before another if a signal could travel from the first to the second at or below the speed of light. Lamport realized distributed systems had the same structure: one event happens before another if a message could have traveled between them.

"The notion of happens-before is exactly the same as in relativity except instead of things traveling at the speed of light, it's whether the first event could have affected the other by information sent over messages that were actually sent in the system," he explains.

The paper included another idea—that you could build any distributed system as a state machine—but that part was "completely ignored." Twice, people told Lamport there was nothing in the paper about state machines. He had to reread it to confirm he wasn't going crazy. (It was there.)

This pattern—of the 'obvious' insight being the important one, and the important one being overlooked—defines much of Lamport's career. People got excited about happens-before relationships. They wrote papers on partial orderings. But the practical method that actually works for understanding concurrent systems? State invariants. The thing that seemed too simple to emphasize.

The Gift Nobody Sees

What does it mean to have a gift of abstraction? In Lamport's case, it meant taking the deli counter and seeing mutual exclusion, taking Einstein's space-time and seeing distributed consensus, taking a complex coordination problem and realizing one piece could just... go away.

"If you think you know something but don't write it down, you only think you know it," Lamport says—a principle he's lived by throughout his career. Writing forces clarity. It exposes the gaps between thinking you understand something and actually understanding it.

The irony is that this gift, which earned Lamport computing's highest honor, is the same quality that kept him from recognizing his own intelligence. When every complex problem resolves into something simple once you see it right, of course it seems obvious. Of course anyone could have done it.

Except they didn't.

—Marcus Chen-Ramirez