Edsger Dijkstra invented the formal theory of concurrent programming in a 1965 paper by introducing the concept of critical sections—pieces of code that at most one process can execute at a time—as a way to structure programs as collections of semi-independent tasks that must synchronize.

If you think you know something but don't write it down, you only think you know it because writing forces you to confront gaps in reasoning that seem obvious in your head but collapse on paper.

The origin of the time-sharing problem was that computers were expensive and fast, so they could be used simultaneously by multiple people whose programs would compete for shared resources like printers, requiring synchronization to prevent garbled output.

Lamport submitted a simple two-process algorithm to CACM in 1972, received a letter pointing out a bug, and realized that concurrent programs are hard to get right and require proofs of correctness—this rejection motivated him to develop the bakery algorithm.

The bakery algorithm was inspired by the deli ticket system, where customers take a numbered ticket and the lowest remaining number is served next, adapted to work without central control by having each process choose its own ticket number.

The bakery algorithm has the remarkable property that it does not require atomic (all-or-nothing) writes to shared memory: if one process reads a register while another is writing to it, the reader can get any arbitrary value and the algorithm still works correctly.

When Lamport shared the bakery algorithm proof with colleague Anatol Hol, the result was so remarkable that Hol didn't believe it, took it home to find the error, but never found anything wrong with it.

Dijkstra's original solution to the critical section problem had the defect that processes could be starved—an individual process might never get access to the critical section if other processes kept entering.

Dijkstra's EWDs (Edsger W. Dijkstra's notes) were informal papers he would write when he had an idea and send out to colleagues and mentees—a network-based mode of knowledge sharing predating email.

Lamport simplified Dijkstra's concurrent garbage collection algorithm by recognizing that the free list handling—which Dijkstra had made a special process—could be integrated into the regular data structure, requiring no special handling.

Dijkstra told Lamport late in his career that he had 'a remarkable ability at abstraction,' which Lamport only recently (after winning the Turing Award) realized was the core reason for his success—not raw intelligence, but exceptional abstraction ability.

In 1976, Lamport visited the Netherlands and worked with Carl Holt (not Dijkstra directly) for a month, meeting with Dijkstra once a week, and produced one published paper—a variant of the bakery algorithm—as the only tangible result.

Lamport drew the notion of 'happens before' from special relativity: just as one event can influence another via light-speed-limited signals in physics, in distributed systems one event can influence another via messages actually sent in the system; this is the fundamental notion of causality in distributed computing.

In the Time, Clocks paper, Lamport described systems in terms of state machines—entities with a state that processes commands in order, where each command changes state and produces a value—and recognized this was the most important idea in the paper, but it was completely ignored by readers.

Understanding a concurrent program requires identifying invariants—boolean-valued properties of the state that, if true at each step, guarantee the output is correct—and reasoning about invariants rather than behavioral sequences reduces complexity from exponential to quadratic in the number of processes.

Much research in distributed systems theory attempts to use partial orderings and behavioral proofs, which is not the practical way to build systems; the method that reliably works is invariance proofs, though there are exceptions like the bakery algorithm where partial orderings are useful.

The Byzantine generals problem arose from Lamport's work on fault-tolerant state machines at SRI, where the challenge was how systems could reach agreement when some processes might fail arbitrarily (do 'anything')—including sending malicious or contradictory messages.

Lamport's initial digital signature algorithm was impractical because it required roughly 128 bits to sign a single bit of data; however, by hashing documents first (using a one-way hash that cannot be forged or reversed), the overhead becomes manageable.

Lamport's initial Byzantine generals algorithm used digital signatures, which allowed it to tolerate one faulty process with three total processes, whereas algorithms without signatures required four processes—a critical difference for practical systems.

At the time (1975) Lamport developed his Byzantine algorithm, very few people knew about digital signatures; he learned about them from Whitfield Diffie, a friend, who described the unsolved problem of how to sign messages; Lamport sat down and sketched out the first digital signature algorithm on a napkin.