On Formally Undecidable Propositions of Principia Mathematica and Related Systems (1931)
Kurt Godel's 1931 paper proving the incompleteness theorems: any consistent formal system rich enough for arithmetic contains true statements it cannot prove.
Landmark Papers
What the papers actually said - linked to the originals.
43 entries, all primary-sourced
On Computable Numbers, with an Application to the Entscheidungsproblem (1936)
Alan Turing's 1936 paper that introduced the Turing machine and proved that some problems, including the decision problem for logic, are undecidable.
First Draft of a Report on the EDVAC (1945)
John von Neumann's 1945 report that laid out the stored-program architecture, describing a computer with a single memory for both instructions and data plus arithmetic, control, and input/output units.
A Mathematical Theory of Communication (1948)
Claude Shannon's foundational 1948 paper in the Bell System Technical Journal, which introduced the bit, entropy, and channel capacity and founded information theory.
The FORTRAN Automatic Coding System (1957)
The 1957 conference paper by Backus and colleagues that described the design of the FORTRAN language and its optimizing compiler for the IBM 704.
The Art of Computer Programming
Donald Knuth's multi-volume work, begun in the early 1960s, that became the definitive reference on algorithms and their mathematical analysis.
Go To Statement Considered Harmful (1968)
Edsger Dijkstra's short letter arguing that the unrestricted go to statement makes programs hard to understand, published in the Communications of the ACM in March 1968.
A Relational Model of Data for Large Shared Data Banks (1970)
E. F. Codd's June 1970 CACM paper that introduced the relational model and founded the field of relational databases.
Cook, The Complexity of Theorem-Proving Procedures (1971)
Stephen Cook's STOC 1971 paper that introduced NP-completeness and proved the satisfiability problem is NP-complete.
Reducibility Among Combinatorial Problems (1972)
Richard Karp's paper proving 21 important combinatorial problems NP-complete and showing how widespread NP-completeness is.
On the Criteria To Be Used in Decomposing Systems into Modules
David Parnas's 1972 paper that introduced information hiding as the right basis for splitting a software system into modules.
A Protocol for Packet Network Intercommunication (1974)
The 1974 Cerf and Kahn paper in IEEE Transactions on Communications that introduced the Transmission Control Protocol and the gateway concept for joining separate packet networks into an internetwork.
The UNIX Time-Sharing System (1974)
Ritchie and Thompson's 1974 CACM paper that introduced Unix to the world and described its file system, processes, and command shell.
The Mythical Man-Month: Essays on Software Engineering
Fred Brooks's 1975 collection of essays, drawn from managing IBM's OS/360, on why large software projects are so hard to schedule and manage.
Ethernet: Distributed Packet Switching for Local Computer Networks (1976)
Metcalfe and Boggs's July 1976 Communications of the ACM paper that introduced Ethernet and the design of the local-area network to the world.
New Directions in Cryptography (1976)
Diffie and Hellman's 1976 paper that introduced public-key cryptography, public key exchange, and digital signatures.
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
The 1978 paper by Rivest, Shamir, and Adleman that introduced the RSA cryptosystem.
Time, Clocks, and the Ordering of Events in a Distributed System (1978)
Leslie Lamport's landmark 1978 paper introducing logical clocks and the happens-before relation, one of the most-cited works in computer science.
An Improved Illumination Model for Shaded Display (Whitted, 1980)
Turner Whitted's 1980 Communications of the ACM paper that introduced recursive ray tracing, generating mirror reflection, refraction, and shadows from a single global illumination model.
The Transaction Concept: Virtues and Limitations (1981)
Jim Gray's 1981 VLDB paper that crystallized the transaction as a programming abstraction with the properties of atomicity, durability, and consistency.
The Byzantine Generals Problem (Lamport, Shostak, Pease, 1982)
The 1982 paper by Lamport, Shostak, and Pease that framed the problem of reaching agreement among distributed participants when some of them may be traitors sending conflicting messages.
Reflections on Trusting Trust
Ken Thompson's 1984 Turing Award lecture, which shows how a compiler can be rigged to insert a hidden backdoor that survives even after the malicious source code is removed, and asks how far we can ever trust software we did not write ourselves.
Structure and Interpretation of Computer Programs (SICP)
The influential MIT textbook by Abelson and Sussman that taught programming through Scheme, abstraction, and composition.
The GNU Manifesto
Richard Stallman's 1985 essay announcing the GNU Project and arguing the ethical and practical case for a complete free operating system that users are free to run, study, share, and modify.
Impossibility of Distributed Consensus with One Faulty Process (FLP, 1985)
The 1985 Fischer, Lynch, and Paterson paper that proved no deterministic asynchronous consensus protocol can tolerate even a single crash failure and still always terminate.
An O(ND) Difference Algorithm and Its Variations (1986)
Eugene Myers's 1986 paper describing a fast, minimal-edit difference algorithm that most modern diff and version-control tools use to compute the smallest set of changes between two files.
No Silver Bullet - Essence and Accident in Software Engineering
Fred Brooks's 1986 paper arguing that no single advance will deliver a tenfold improvement in software productivity, because software's hardest problems are essential, not incidental.
Information Management: A Proposal (1989)
Tim Berners-Lee's 1989 CERN proposal document that founded the World Wide Web, famously annotated by his manager Mike Sendall as 'Vague but exciting.'
Introduction to Algorithms (CLRS)
The standard university algorithms textbook by Cormen, Leiserson, Rivest, and Stein, first published in 1990 and universally known as CLRS.
Why Functional Programming Matters
John Hughes's influential 1990 essay arguing that higher-order functions and lazy evaluation are the keys to modularity and code reuse.
Design Patterns: Elements of Reusable Object-Oriented Software
The 1994 book by Gamma, Helm, Johnson, and Vlissides - the 'Gang of Four' - that catalogued 23 reusable solutions to common object-oriented design problems.
The Cathedral and the Bazaar
Eric Raymond's 1997 essay contrasting the closed 'cathedral' model of software development with the open, decentralized 'bazaar' model of Linux; it influenced Netscape's decision to open-source its browser.
The Part-Time Parliament and Paxos Made Simple
Leslie Lamport's two papers that first presented the Paxos consensus protocol and then re-explained it in plainer terms.
Refactoring: Improving the Design of Existing Code
Martin Fowler's landmark 1999 book that named and catalogued individual refactorings and made disciplined, behavior-preserving code improvement mainstream practice.
Architectural Styles and the Design of Network-based Software Architectures
Roy Fielding's 2000 UC Irvine PhD dissertation, whose Chapter 5 defines the REST architectural style.
Brewer's CAP Conjecture and Its Proof
Eric Brewer's CAP conjecture from his 2000 PODC keynote, formally proven by Gilbert and Lynch in 2002, and revisited by Brewer in his 2012 article on how the rules had changed.
The Manifesto for Agile Software Development
A short 2001 statement of four values and twelve principles, written by seventeen practitioners, that named and reframed how most software is built.
The Google File System
Google's 2003 paper describing a fault-tolerant distributed filesystem that stores huge datasets across thousands of cheap commodity machines.
MapReduce: Simplified Data Processing on Large Clusters
Jeff Dean and Sanjay Ghemawat's 2004 paper introducing a simple programming model that hides the hard parts of running batch computations across thousands of machines.
Bigtable: A Distributed Storage System for Structured Data
Google's 2006 paper describing a distributed storage system for structured data that scales to petabytes across thousands of machines and inspired wide-column stores like HBase and Cassandra.
Dynamo: Amazon's Highly Available Key-value Store
Amazon's 2007 paper describing Dynamo, a distributed key-value store that traded strong consistency for high availability and inspired Cassandra, Riak, and DynamoDB.
Spanner: Google's Globally-Distributed Database
The paper describing the first database to provide externally-consistent distributed transactions at global scale, using a clock API called TrueTime.
In Search of an Understandable Consensus Algorithm
The 2014 USENIX ATC paper by Diego Ongaro and John Ousterhout that introduced the Raft consensus algorithm and explicitly optimized for understandability.