Foundational Computer Science Papers — A Reading Plan

I had claude list papers to refresh my CS knowledge as I have been doing too little CS theory for many years.

Phase 0 — Learn to read papers

• S. Keshav — “How to Read a Paper” (2007) — PDF · ACM DL

Phase 1 — What computation is

• Alan Turing — “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936) — PDF
  Genuinely hard. Read Petzold’s The Annotated Turing alongside it or you’ll bounce.

• Claude Shannon — “A Mathematical Theory of Communication” (1948) — Bell System Technical Journal
  Read at least through the discrete-channel sections.

• Stephen Cook — “The Complexity of Theorem-Proving Procedures” (1971) — ACM DL

• Richard Karp — “Reducibility Among Combinatorial Problems” (1972) — Springer
  Read Cook then Karp back to back: NP-completeness arriving, then immediately eating the world.

• Alan Turing — “Computing Machinery and Intelligence” (1950) — Mind, Oxford Academic
  Short, and much better than its reputation as “the Turing test paper.”

Phase 2 — Structure and abstraction

• David Parnas — “On the Criteria To Be Used in Decomposing Systems into Modules” (1972) — CACM (free) · ACM DL
  Still the best thing ever written about modularity. Source of “information hiding.”

• Edsger Dijkstra — “Go To Statement Considered Harmful” (1968) — ACM DL · original as EWD215 in the E.W. Dijkstra Archive

• Edsger Dijkstra — “Cooperating Sequential Processes” (1965/1968) — no stable free link; EWD123, findable in the Dijkstra Archive. Where semaphores and the concurrency primitives come from.

• C.A.R. Hoare — “An Axiomatic Basis for Computer Programming” (1969) — ACM DL

• C.A.R. Hoare — “Communicating Sequential Processes” (1978) — CACM 21(8), 666–677; see Hoare’s publication list. The ancestor of Go’s channels and Erlang’s message passing.

• John McCarthy — “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (1960) — Full text at Stanford
  Lisp defined in terms of itself.

• Barbara Liskov & Stephen Zilles — “Programming with Abstract Data Types” (1974) — no stable free link; SIGPLAN Notices 9(4), 50–59.

• John Backus — “Can Programming Be Liberated from the von Neumann Style?” (1978) — ACM DL
  Turing Award lecture. The functional-programming manifesto.

• Robin Milner — “A Theory of Type Polymorphism in Programming” (1978) — no stable free link; JCSS 17(3), 348–375. Optional, but this is where type inference comes from.

Phase 3 — Systems

• Ritchie & Thompson — “The UNIX Time-Sharing System” (1974) — PDF (Bell Labs) · ACM DL

• E.F. Codd — “A Relational Model of Data for Large Shared Data Banks” (1970) — CACM (free) · ACM DL

• Saltzer, Reed & Clark — “End-to-End Arguments in System Design” (1984) — PDF (MIT)
  Read it twice. It’s an argument about where to put things, and it generalizes far past networking.

• Butler Lampson — “Hints for Computer System Design” (1983) — PDF · abstract
  The closest thing the field has to accumulated wisdom in list form.

• Leslie Lamport — “Time, Clocks, and the Ordering of Events in a Distributed System” (1978) — PDF

• Fischer, Lynch & Paterson — “Impossibility of Distributed Consensus with One Faulty Process” (1985) — PDF (MIT CSAIL)

• Lamport, Shostak & Pease — “The Byzantine Generals Problem” (1982) — PDF

• Leslie Lamport — “Paxos Made Simple” (2001) — PDF
  Read this rather than the original Part-Time Parliament paper.

• Jim Gray — “The Transaction Concept: Virtues and Limitations” (1981) — no stable free link; Proc. VLDB 1981, 144–154.

• Dean & Ghemawat — “MapReduce: Simplified Data Processing on Large Clusters” (2004) — PDF (USENIX)

• DeCandia et al. — “Dynamo: Amazon’s Highly Available Key-value Store” (2007) — PDF
  MapReduce and Dynamo are the modern applications of everything above them in this phase.

Phase 4 — Security, and the machines that fooled us

• Saltzer & Schroeder — “The Protection of Information in Computer Systems” (1975) — Full text
  The design principles section is the part everyone still cites.

• Diffie & Hellman — “New Directions in Cryptography” (1976) — PDF (Stanford)

• Rivest, Shamir & Adleman — “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” (1978) — PDF (MIT)

• Ken Thompson — “Reflections on Trusting Trust” (1984) — PDF

Phase 5 — Where the machine meets the person

• Vannevar Bush — “As We May Think” (1945) — The Atlantic

• Douglas Engelbart — “Augmenting Human Intellect: A Conceptual Framework” (1962) — Doug Engelbart Institute
  Long. The framework sections are the ones to read.

• Ivan Sutherland — “Sketchpad: A Man-Machine Graphical Communication System” (1963) — PDF (Cambridge TR-574)