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