One of the things I love about working in Computer Science is that it is a relatively young field. Except for Charles Babbage, almost all the work that matters was done by people no older than my father. I love to read some of the older papers in CS, partly because I'm interested in the history of the field, and partly because they give a wonderful perspective on how things we take for granted, such as high level languages, memory hierarchies, binary arithmetic, etc. were discovered and invented.
The following is in no way a comprehensive or balanced list of CS readings. Rather, it's a list of some papers, mostly on "systems", that I find to be particularly interesting, well written, of unusual historical significance, or just under-appreciated. A few are quite obvious or well known, but I've tried to emphasize some that may be less familiar, especially to those who started their work in CS more recently.
Computer Programming as an Art (Turing Award Lecture)
Publication date: 1974
(pdf)
Donald Knuth's legendary series The Art of Computer Programming is arguably the Bible of computer science, but in this Turing award lecture Don just talks about the joy of coding, and about the art and science of writing beautiful programs.
Why Alto?
Publication date: December 19, 1972
(pdf)
Xerox PARC's role in creating multimedia personal computers, WYSIWYG user interfaces, object-oriented languages, and local area networks is legendary. This is the memo that Butler Lampson wrote to Xerox management, proposing the development of a network of Altos, the personal computer on which all of this work was done. The paper is noteworthy not particularly for technical details discussed (see the Bitsaver's Alto site for the core Alto specifications: HW pt1 & pt2, SW pt1 & pt2), but for the milestone that it represents: this is the note that led to the construction of the first LAN-connected personal computers that resemble the Macintosh's and Windows machines we take for granted today. These were the first machines that could, in a truly natural way, handle graphics, images and even musical scores, along with multifont text.
I first used the Altos in 1978, when they were installed at the Stanford CS department. Although they had been available inside Xerox for some time, it is hard now to appreciate just how revolutionary they were. The Bravo editor, created for the Alto, was the first one that allowed direct manipulation of the image of the printed page, with multiple fonts, font sizes, and faces. Smalltalk was invented to run on this machine. Quote: If our theories about the utility of cheap, powerful personal computers are correct, we should be able to demonstrate them convincingly on Alto. Indeed.
Hints for Computer System Design
ACM Operating Systems Rev. 15, 5 (Oct. 1983), pp 33-48. Reprinted in IEEE Software 1, 1 (Jan. 1984), pp 11-28
(pdf)
Another great paper from Butler, though in a very different style. This paper has become quite famous, but I'm particularly fond of it for a personal reason: it was presented at the 1983 SOSP Conference in Bretton Woods, the first serious academic conference in CS that I attended. It was at this conference that I met and became part of a community of researchers with whom I stayed involved with for many years (I think I attended all the SOSPs after that for nearly 15 years). Anyway, this is a paper that doesn't just give small practical hints; it teaches one how to develop good intuitions about system design.
Gaining Efficiency in Transport Services by Appropriate Design and Implementation Choices
ACM Transactions on Computer Systems (TOCS), Volume 5 Issue 2, May 1987
I don't think we've ever met, but Dick Watson is one of my favorite computer scientists, and like much of his work, this paper is thought-provoking and very original. The key is summed up in one important quote: a common mistake is to take a layered design as a requirement for a correspondingly layered implementation. In other words: layering your implementation to match your system's core abstractions will likely give you a clean and flexible result, but often one that is slower than necessary (and perhaps by orders of magnitude!) Many, many important optimizations, whether in compiler back ends, networking systems (the main subject of the paper), or storage systems work across layers. This is a truly important message: unfortunately, clean structure can hurt performance.
The Google Filesystem
Title: The Google File System
Publication date: October, 2003
ACM Symposium on Operating System Principles (SOSP), October 2003
(pdf)
The GFS paper was the first to show how Google built a new form of scalable, fault-tolerant, massively parallel distributed computing system, using commodity as opposed to server-grade components, running on hundreds of thousands of nodes, and for a global community of users. Furthermore, GFS illustrates a key point: for maximum scalability and fault tolerance in a storage system, you very often want weak consistency or even a degree of unreliability — GFS reserves the right to lose appends if a disk drive is lost before replication occurs. The Google work shows how large servers will be built in the coming decades: a wonderful, truly important paper.
From 1988 to 1992, 15 years before the GFS publication, I worked at IBM on a system named Datacube. Though only a 10-node prototype, it was one of the earliest experiments with architecting a massively-parallel data- (as opposed to numeric-) processing system using commodity processors, memories, and disks. We built a fault tolerant distributed filesystem using RAID technologies, etc. Our work in no way influenced GFS or the Googleplex, as far as I know, but the underlying philosophies are similar: commodity components, massive scale and parallelism, fault tolerance to maintain availability when those commodity components fail. The Google work is tremendously important in any case, but I was particularly gratified to see them realize in practice the same vision with which we had experimented many years before.
First Draft of a Report on the Edvac
Publication date: June 30, 1945
LaTex transcription of the original: (pdf)
Written just after WW II, two years before the AT&T transistor work, and when ENIAC had been operational only a short time, this paper set out with astonishing foresight the majority of the computer architecture tradeoffs that would concern the field for at least 40 years. Many of them, such as how to balance memory hierarchies, whether to apply scarce hardware to simple fast circuits or to more complex parallel ones, and more fundamentally how to think about such tradeoffs, remain important questions over 60 years later. I've heard some debate as to how much of this represents von Neumann's personal brilliance, and how much is a synthesis of discussions with several others, but it's an astonishing piece of work either way.
End to End Arguments in System Design
Publication date: November, 1984
ACM Transactions in Computer Systems 2, 4, November, 1984, pages 277-288
(pdf)
Not only is this a wonderfully visionary paper on how to think about reliability and error recovery in a wide variety of computer data manipulation systems, it forms the key philosophical underpinning for the Internet as we know it. These were the "arguments" used to justify building a reliable system out of unreliable datagrams, and crucially, to justify putting the smarts at the periphery of the Internet vs. in the network itself (traditional AT&T phone systems). Thus, indirectly, this paper justifies building networks in which you can innovate by providing new functions (e.g. the Web, BitTorrent, VOIP, etc.) without necessarily rearchitecting or redeploying the infrastructure that implements the network fabric.
There have been at least two followup commentaries by the authors: in 1998, all three authors collaborated on Active Networking and End-To-End Arguments; in 2001, David Clark and Marjory Blumenthal revisited some of these topics in Rethinking the Design of the Internet: The End-to-End Arguments vs. the Brave New World.
The original LISP paper
Title: Recursive Functions of Symbolic Expressions and Their Computation by Machine (Part 1)
Publication date: April, 1960
(pdf)
In just a few pages, this paper motivates the creation of high level lanaguges for doing symbolic manipulation, builds up a mathematical framework for such languages, uses that to define LISP itself, and goes from there to a a language that can interpret its own definition. A true classic of the CS literature. (It's interesting to note how much influence LISP continues to have on the design of modern languages including Python, PHP, and many others.)
RPC
Title: Implementing Remote Procedure Calls
Publication date: February, 1984
ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984, Pages 39-59
(pdf)
This paper, the TOCS follow-on to Bruce's PhD thesis, essentially put RPC on the map as a major focus for structuring distributed systems. I thought at the time and continue to think that language-integrated RPC is somewhat overemphasized in all this at the expense of things like asynchronous message passing and language-independent request/response (e.g. HTTP), but this was a tremendously influential paper and is very well done. Bruce was a fine CS researcher who is very much missed.
Decimal Algorism
Title: Decimal Floating-Point: Algorism for Computers
Publication date: June, 2003
16th IEEE Symposium on Computer Arithmetic (ARITH-16 '03)
(pdf)
This paper, by my good friend Mike Cowlishaw, does a great job of exploring the history of the decimal/binary tradeoff, deals with everything from technical to social issues, and sets out a vision for what needs to be done in both hardware and software. Though in some ways of narrower interest than many of the other listed here, this is a lovely paper, beautifully documented and presented.