The hundred
The seed list, in its own numbering.
100 papers, in the order to read them. A paper that needs another one first is listed under it.
- 1On Computable Numbers, with an Application to the Entscheidungsproblem
the universal machine and the undecidability of the halting problem
- 2A Mathematical Theory of Communication
entropy, channel capacity, and the separation of source and channel coding
- 3Error Detecting and Error Correcting Codes
minimum distance, and codes that repair what they detect
Read first: A Mathematical Theory of Communication
- 4Finite Automata and Their Decision Problems
nondeterministic automata, and the subset construction that removes it
- 5Relationships Between Nondeterministic and Deterministic Tape Complexities
Savitch's theorem: NSPACE(f) is in DSPACE(f squared)
- 6The Complexity of Theorem-Proving Procedures
NP-completeness, and SAT as the first complete problem
- 7Reducibility Among Combinatorial Problems
twenty-one problems reduced to one another, making NP-completeness a tool
Read first: The Complexity of Theorem-Proving Procedures
- 8The Knowledge Complexity of Interactive Proof-Systems
interactive proofs, and proving a statement while revealing nothing else
- 9IP = PSPACE
interaction with randomness buys exactly polynomial space
Read first: The Knowledge Complexity of Interactive Proof-Systems
- 10Natural Proofs
why the circuit lower-bound techniques that existed could not settle P vs NP
- 11
- 12A Note on Two Problems in Connexion with Graphs
single-source shortest paths, and a minimum spanning tree, in three pages
- 13
- 14
- 15An Algorithm for the Machine Calculation of Complex Fourier Series
the discrete Fourier transform in n log n
- 16Space/Time Trade-offs in Hash Coding with Allowable Errors
a set membership test that is wrong only in one direction
- 17Depth-First Search and Linear Graph Algorithms
strongly connected components in one pass
- 18Efficient String Matching: An Aid to Bibliographic Search
many patterns at once, with failure links over a trie
- 19
- 20The Anatomy of a Large-Scale Hypertextual Web Search Engine
rank a page by the ranks of the pages that link to it
- 21Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
programs as data, and eval written in itself
- 22An Axiomatic Basis for Computer Programming
preconditions, postconditions, and a proof rule per statement
- 23Scheme: An Interpreter for Extended Lambda Calculus
lexical scope, first-class procedures, and tail calls
Read first: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
- 24A Theory of Type Polymorphism in Programming
principal types, inferred without annotation
- 25Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs
the assignment statement as the bottleneck, and programs combined algebraically
- 26Efficient Implementation of the Smalltalk-80 System
dynamic translation and inline caches, the ancestor of every JIT
- 27Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
dominance frontiers, and one definition per name
- 28Constant Propagation with Conditional Branches
constants and unreachable branches found in one lattice walk
Read first: Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
- 29LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation
a typed SSA intermediate representation as a durable artefact
Read first: Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
- 30Trace-based Just-in-Time Type Specialization for Dynamic Languages
compile hot loop traces, not methods
Read first: Efficient Implementation of the Smalltalk-80 System
- 31The Structure of the "THE"-Multiprogramming System
layers, each provable against the one below it
- 32The Working Set Model for Program Behavior
locality made measurable, and thrashing explained
- 33The UNIX Time-Sharing System
everything is a file, and the system is small enough to describe
- 34Time, Clocks, and the Ordering of Events in a Distributed System
happens-before, logical clocks, and state machine replication
- 35End-To-End Arguments in System Design
a function belongs at the endpoints unless the network can finish the job
- 36Implementing Remote Procedure Calls
a call that crosses a machine, and everything that makes it not a call
- 37The Part-Time Parliament
consensus that survives any minority failing, told as an archaeology paper
Read first: Time, Clocks, and the Ordering of Events in a Distributed System
- 38Xen and the Art of Virtualization
paravirtualization, trading a modified guest for near-native speed
- 39
- 40MapReduce: Simplified Data Processing on Large Clusters
two functions, and the framework handles the thousand machines
Read first: The Google File System
- 41Dynamo: Amazon's Highly Available Key-value Store
always writable, reconciled later, with consistent hashing and vector clocks
- 42In Search of an Understandable Consensus Algorithm
consensus decomposed into leader election, log replication and safety
Read first: The Part-Time Parliament
- 43Large-scale cluster management at Google with Borg
one scheduler for batch and serving, and the ancestor of Kubernetes
- 44A Protocol for Packet Network Intercommunication
gateways between heterogeneous networks, and a common datagram
- 45Ethernet: Distributed Packet Switching for Local Computer Networks
carrier sense, collision detection, and exponential backoff on a shared wire
- 46Congestion Control in IP/TCP Internetworks
small packets coalesced, and congestion collapse named
- 47Congestion Avoidance and Control
slow start, congestion avoidance, and the conservation of packets
Read first: Congestion Control in IP/TCP Internetworks
- 48Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks
why additive increase and multiplicative decrease converges to fairness
Read first: Congestion Avoidance and Control
- 49Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
consistent hashing on a ring, with a finger table for log n hops
- 50OpenFlow: Enabling Innovation in Campus Networks
separate the control plane from the switch
- 51P4: Programming Protocol-Independent Packet Processors
the data plane described by a program rather than fixed in silicon
Read first: OpenFlow: Enabling Innovation in Campus Networks
- 52A Relational Model of Data for Large Shared Data Banks
data as relations, independent of how it is stored
- 53Organization and Maintenance of Large Ordered Indices
a balanced tree with a page-sized node
- 54System R: Relational Approach to Database Management
the first relational system that worked, and SQL with it
Read first: A Relational Model of Data for Large Shared Data Banks
- 55Access Path Selection in a Relational Database Management System
cost-based optimisation, and dynamic programming over join orders
Read first: System R: Relational Approach to Database Management
- 56The Gamma Database Machine Project
shared-nothing parallelism, and hash partitioning that scales linearly
- 57ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging
analysis, redo, undo, and repeating history before undoing it
- 58Volcano - An Extensible and Parallel Query Evaluation System
the iterator model, and parallelism as one more operator
- 59C-Store: A Column-oriented DBMS
store columns, compress them, and read only what the query touches
- 60MonetDB/X100: Hyper-Pipelining Query Execution
vectors of tuples per call, so the CPU pipeline stays full
Read first: Volcano - An Extensible and Parallel Query Evaluation System
- 61Bigtable: A Distributed Storage System for Structured Data
a sparse, sorted, multidimensional map over a distributed file system
Read first: The Google File System
- 62Spanner: Google's Globally-Distributed Database
TrueTime, and externally consistent transactions across continents
Read first: Bigtable: A Distributed Storage System for Structured Data, The Part-Time Parliament
- 63The Snowflake Elastic Data Warehouse
storage and compute separated, and elasticity as a product
Read first: C-Store: A Column-oriented DBMS
- 64Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities
the serial fraction bounds every speedup
- 65An Efficient Algorithm for Exploiting Multiple Arithmetic Units
register renaming and the common data bus, i.e. out-of-order execution
- 66Design of Ion-Implanted MOSFET's with Very Small Physical Dimensions
shrink every dimension and the power density stays put, until it did not
- 67RISC I: A Reduced Instruction Set VLSI Computer
fewer instructions, executed faster, with the compiler taking the slack
- 68Improving Direct-Mapped Cache Performance by the Addition of a Small Fully-Associative Cache and Prefetch Buffers
a tiny victim cache removes most conflict misses
- 69Two-Level Adaptive Training Branch Prediction
a history register indexing a pattern table
- 70In-Datacenter Performance Analysis of a Tensor Processing Unit
a systolic matrix unit, and the roofline that explains it
- 71The Protection of Information in Computer Systems
eight design principles, least privilege among them
- 72New Directions in Cryptography
a shared secret agreed in public, and the idea of a public key
- 73Using Encryption for Authentication in Large Networks of Computers
nonces, a trusted third party, and the protocol that taught the field to look for flaws
- 74A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
trapdoor one-way functions from the difficulty of factoring
Read first: New Directions in Cryptography
- 75Probabilistic Encryption
semantic security, and why deterministic encryption cannot have it
Read first: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
- 76Kerberos: An Authentication Service for Open Network Systems
tickets from a key distribution centre, deployed for real
Read first: Using Encryption for Authentication in Large Networks of Computers
- 77Practical Byzantine Fault Tolerance
agreement with a third of the replicas lying, at a usable cost
Read first: The Part-Time Parliament
- 78Bitcoin: A Peer-to-Peer Electronic Cash System
proof of work as Sybil resistance, and the longest chain as the truth
- 79Computing Machinery and Intelligence
the imitation game, and nine objections answered
- 80The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain
a learning rule for a linear threshold unit
- 81Learning Representations by Back-propagating Errors
the chain rule applied to a layered network
Read first: The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain
- 82
- 83A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
many weak learners, reweighted, add up to a strong one
- 84Gradient-Based Learning Applied to Document Recognition
convolution, weight sharing and pooling, trained end to end
Read first: Learning Representations by Back-propagating Errors
- 85ImageNet Classification with Deep Convolutional Neural Networks
depth, ReLU, dropout and two GPUs
Read first: Gradient-Based Learning Applied to Document Recognition
- 86Generative Adversarial Nets
a generator and a discriminator playing a minimax game
- 87Sequence to Sequence Learning with Neural Networks
an encoder LSTM into a decoder LSTM, with no alignment model
- 88Deep Residual Learning for Image Recognition
learn the residual, and a hundred layers become trainable
Read first: ImageNet Classification with Deep Convolutional Neural Networks
- 89Mastering the game of Go with deep neural networks and tree search
policy and value networks guiding Monte Carlo tree search
- 90Attention Is All You Need
self-attention alone, with no recurrence and no convolution
Read first: Sequence to Sequence Learning with Neural Networks
- 91BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
masked language modelling, then fine-tuning
Read first: Attention Is All You Need
- 92Language Models are Few-Shot Learners
scale, and a task specified in the prompt rather than the weights
Read first: Attention Is All You Need
- 93Sketchpad: A Man-Machine Graphical Communication System
drawing with constraints, and the first interactive graphics system
- 94A Research Center for Augmenting Human Intellect
the mouse, hypertext, and screen editing, shown working
- 95Illumination for Computer Generated Pictures
interpolate the normal, not the intensity, and add a specular term
- 96Direct Manipulation: A Step Beyond Programming Languages
continuous representation, physical action, and reversible operations
Read first: A Research Center for Augmenting Human Intellect
- 97Managing the Development of Large Software Systems
the diagram everyone quotes, and the page after it saying it does not work
- 98On the Criteria To Be Used in Decomposing Systems into Modules
modules hide decisions, not steps
- 99
- 100No Silver Bullet - Essence and Accidents of Software Engineering
essential complexity is irreducible, so no single advance gives an order of magnitude