List of important publications in computer science  

Topics covered: concurrent computing, parallel computing, and distributed computing.

Databases

A relational model for large shared data banks

• E. F. Codd
• Communications of the ACM, 13(6):377–387, June 1970

Description: This paper introduced the relational model for databases. This model became the number one model.

Binary B-Trees for Virtual Memory

• Rudolf Bayer
• ACM-SIGFIDET Workshop 1971, San Diego, California, Session 5B, p. 219–235.

Description: This paper introduced the B-Trees data structure. This model became the number one model.

Relational Completeness of Data Base Sublanguages

• E. F. Codd
• In: R. Rustin (ed.): Database Systems: 65–98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972)
• Online version (PDF)

Description: Completeness of Data Base Sublanguages

The Entity Relationship Model – Towards a Unified View of Data

• Peter Chen
• ACM Transactions on Database Systems, Vol. 1, No. 1, March 1976, pp. 9–36

Description: This paper introduced the entity-relationship diagram(ERD) method of database design.

SEQUEL: A structured English query language

• Donald D. Chamberlin, Raymond F. Boyce
• International Conference on Management of Data, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, Ann Arbor, Michigan, pp. 249–264

Description: This paper introduced the SQL language.

The notions of consistency and predicate locks in a database system

• K.P. Eswaran, Jim Gray, R.A. Lorie, I.L. Traiger
• Communications of the ACM 19, 1976, 624—633

Description: This paper defined the concepts of transaction, consistency and schedule. It also argued that a transaction needs to lock a logical rather than a physical subset of the database.

Federated database systems for managing distributed, heterogeneous, and autonomous databases

• Amit Sheth, J.A. Larson,"
• ACM Computing Surveys - Special issue on heterogeneous databases Surveys, Volume 22 Issue 3, Pages 183 - 236, Sept. 1990
• ACM source

Description: Introduced federated database systems concept leading huge impact on data interoperability and integration of hetereogeneous data sources.

Mining association rules between sets of items in large databases

• Rakesh Agrawal, Tomasz Imielinski, Arun Swami
• Proc. of the ACM SIGMOD Conference on Management of Data, pages 207–216, Washington, D.C., May 1993
• Online copy (HTML)

Description: Association rules, a very common method for data mining.

History of computation

The Computer from Pascal to von Neumann

• Template:Cite book

Description: Perhaps the first book on the history of computation.

A History of Computing in the Twentieth Century

edited by:

• Nicholas Metropolis
• J. Howlett
• Gian-Carlo Rota
• Academic Press, 1980, Template:ISBN

Description: Several chapters by pioneers of computing.

Information retrieval

A Vector Space Model for Automatic Indexing

• Gerard Salton, A. Wong, C. S. Yang
• Commun. ACM 18(11): 613–620 (1975)

Description: Presented the vector space model.

Extended Boolean Information Retrieval

• Gerard Salton, Edward A. Fox, Harry Wu
• Commun. ACM 26(11): 1022–1036 (1983)

Description: Presented the inverted index

A Statistical Interpretation of Term Specificity and Its Application in Retrieval

• Karen Spärck Jones
• Journal of Documentation 28: 11–21 (1972). Template:Doi.

Description: Conceived a statistical interpretation of term specificity called Inverse document frequency (IDF), which became a cornerstone of term weighting.

Networking

Data Communications and Networking

• Behrouz A. Forouzan. Template:ISBN, Copyright year: 2013, Publisher:: McGraw hill education.<ref name=":0">{{

1. if: {{#if: http://highered.mheducation.com/sites/0073376221/information_center_view0/index.html | {{#if: Data communication and networking book |1}}}}

 ||Error on call to Template:cite web: Parameters url and title must be specified

}}{{

1. if:

 | {{#if: {{#if: | {{#if:  |1}}}}
   ||Error on call to template:cite web: Parameters archiveurl and archivedate must be both specified or both omitted

}} }}{{#if: Behrouz Forouzan

 | {{#if: 
   | [[{{{authorlink}}}|{{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | Behrouz Forouzan
   }}]]
   | {{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | Behrouz Forouzan
   }}
 }}

}}{{#if: Behrouz Forouzan

 | {{#if: | ; {{{coauthors}}} }}

}}{{#if: Behrouz Forouzan|

   {{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 |}}

}}{{#if: Behrouz Forouzan

 | . }}{{
 #if: 
 |  {{{editor}}}: 

}}{{#if:

   | {{#if:  | {{#if: Data communication and networking book | [{{{archiveurl}}} Data communication and networking book] }}}}
   | {{#if: http://highered.mheducation.com/sites/0073376221/information_center_view0/index.html | {{#if: Data communication and networking book | Data communication and networking book }}}}

}}{{#if: | ({{{language}}}) }}{{#if:

 |  ()

}}{{#if:

 | . {{{work}}}

}}{{#if:

 |  {{{pages}}}

}}{{#if: McGrawhill Education

 | . McGrawhill Education{{#if: Behrouz Forouzan
   | 
   | {{#if:  || }}
 }}

}}{{#if: Behrouz Forouzan

 ||{{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 }}

}}.{{#if:

 |  Archived from the original on [[{{{archivedate}}}]].

}}{{#if: 1 Jan 2013

 |  Retrieved on {{#time:Y F j|1 Jan 2013{{#if:  | , {{{accessyear}}}}}}}.

}}{{#if:

 |  Retrieved on {{{accessmonthday}}}, {{{accessyear}}}.

}}{{#if:

 |  Retrieved on {{{accessdaymonth}}} {{{accessyear}}}.

}}{{#if:

 |  “{{{quote}}}”

}}</ref>

Description: This book presents a comprehensive and accessible approach to data communications and networking that has made this book a favorite with students and professionals alike. More than 830 figures and 150 tables accompany the text and provide a visual and intuitive opportunity for understanding the material.

Operating systems

An experimental timesharing system.

• Fernando J. Corbató, M. Merwin-Daggett, and R.C. Daley
• Proceedings of the AFIPS FJCC, pages 335–344, 1962.
• Online copy (HTML)

Description: This paper discuss time-sharing as a method of sharing computer resource. This idea changed the interaction with computer systems.

The Working Set Model for Program Behavior

• Peter J. Denning
• Communications of the ACM, Vol. 11, No. 5, May 1968, pp 323–333
• Online version(PDF)

Description: The beginning of cache. For more information see SIGOPS Hall of Fame.

Virtual Memory, Processes, and Sharing in MULTICS

• Robert C. Daley, Jack B. Dennis
• Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 306–312.
• Online version(PDF)

Description: The classic paper on Multics, the most ambitious operating system in the early history of computing. Difficult reading, but it describes the implications of trying to build a system that takes information sharing to its logical extreme. Most operating systems since Multics have incorporated a subset of its facilities.

The nucleus of a multiprogramming system

• Per Brinch Hansen
• Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238–242
• Online version(PDF)

Description: Classic paper on the extensible nucleus architecture of the RC 4000 multiprogramming system, and what became known as the operating system kernel and microkernel architecture.

Operating System Principles

• Per Brinch Hansen
• Prentice Hall, Englewood Cliffs, NJ, July 1973
• Online version (ACM Digital Library)

Description: The first comprehensive textbook on operating systems. Includes the first monitor notation (Chapter 7).

A note on the confinement problem

• Butler W. Lampson
• Communications of the ACM, 16(10):613–615, October 1973.
• Online version(PDF)

Description: This paper addresses issues in constraining the flow of information from untrusted programs. It discusses covert channels, but more importantly it addresses the difficulty in obtaining full confinement without making the program itself effectively unusable. The ideas are important when trying to understand containment of malicious code, as well as aspects of trusted computing.

The UNIX Time-Sharing System

• Dennis M. Ritchie and Ken Thompson
• Communications of the ACM 17(7), July 1974.
• Online copy

Description: The Unix operating system and its principles were described in this paper. The main importance is not of the paper but of the operating system, which had tremendous effect on operating system and computer technology.

Weighted voting for replicated data

• David K. Gifford
• Proceedings of the 7th ACM Symposium on Operating Systems Principles, pages 150–159, December 1979. Pacific Grove, California
• Online copy (few formats)

Description: This paper describes the consistency mechanism known as quorum consensus. It is a good example of algorithms that provide a continuous set of options between two alternatives (in this case, between the read-one write-all, and the write-one read-all consistency methods). There have been many variations and improvements by researchers in the years that followed, and it is one of the consistency algorithms that should be understood by all. The options available by choosing different size quorums provide a useful structure for discussing of the core requirements for consistency in distributed systems.

Experiences with Processes and Monitors in Mesa

• Butler W. Lampson, David D. Redell
• Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105–117.
• Online copy (PDF)

Description: This is the classic paper on synchronization techniques, including both alternate approaches and pitfalls.

Scheduling Techniques for Concurrent Systems

• J. K. Ousterhout
• Proceedings of Third International Conference on Distributed Computing Systems, 1982, 22—30.

Description: Algorithms for coscheduling of related processes were given

A Fast File System for UNIX

• Marshall Kirk Mckusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry
• IACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181–197.
• Online copy (PDF)

Description: The file system of UNIX. One of the first papers discussing how to manage disk storage for high-performance file systems. Most file-system research since this paper has been influenced by it, and most high-performance file systems of the last 20 years incorporate techniques from this paper.

The Design of the UNIX Operating System

• Maurice J. Bach, AT&T Bell Labs
• Prentice Hall • 486 pp • Published 05/27/1986

This definitive description principally covered the System V Release 2 kernel, with some new features from Release 3 and BSD.

The Design and Implementation of a Log-Structured File System

• Mendel Rosenblum, J. K. Ousterhout
• ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26–52.
• Online version

Description: Log-structured file system.

Microkernel operating system architecture and Mach

• David L. Black, David B. Golub, Daniel P. Julin, Richard F. Rashid, Richard P. Draves, Randall W. Dean, Alessandro Forin, Joseph Barrera, Hideyuki Tokuda, Gerald Malan, David Bohman
• Proceedings of the USENIX Workshop on Microkernels and Other Kernel Architectures, pages 11–30, April 1992.

Description: This is a good paper discussing one particular microkernel architecture and contrasting it with monolithic kernel design. Mach underlies Mac OS X, and its layered architecture had a significant impact on the design of the Windows NT kernel and modern microkernels like L4. In addition, its memory-mapped files feature was added to many monolithic kernels.

An Implementation of a Log-Structured File System for UNIX

• Margo Seltzer, Keith Bostic, Marshall Kirk McKusick, Carl Staelin
• Proceedings of the Winter 1993 USENIX Conference, San Diego, CA, January 1993, 307-326
• Online version

Description: The paper was the first production-quality implementation of that idea which spawned much additional discussion of the viability and short-comings of log-structured filesystems. While "The Design and Implementation of a Log-Structured File System" was certainly the first, this one was important in bringing the research idea to a usable system.

Soft Updates: A Solution to the Metadata Update problem in File Systems

• G. Ganger, M. McKusick, C. Soules, Y. Patt
• ACM Transactions on Computer Systems 18, 2. pp 127–153, May 2000
• <ref name=":0" />Online version

Description: A new way of maintaining filesystem consistency.

Programming languages

The FORTRAN Automatic Coding System<ref>Template:Harvnb</ref>

• John Backus et al.
• Proceedings of the WJCC (Western Joint Computer Conference), Los Angeles, California, February 1957.
• Online version(PDF)

Description: This paper describes the design and implementation of the first FORTRAN compiler by the IBM team. Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing.

Recursive functions of symbolic expressions and their computation by machine, part I<ref name=Pierce2004/>

• John McCarthy.
• Communications of the ACM, 3(4):184–195, April 1960.
• Several online versions

Description: This paper introduced LISP, the first functional programming language, which was used heavily in many areas of computer science, especially in AI. LISP also has powerful features for manipulating LISP programs within the language.

ALGOL 60

• Revised Report on the Algorithmic Language Algol 60 by Peter Naur, et al. – The very influential ALGOL definition; with the first formally defined syntax.
• Brian Randell and L. J. Russell, ALGOL 60 Implementation: The Translation and Use of ALGOL 60 Programs on a Computer. Academic Press, 1964. The design of the Whetstone Compiler. One of the early published descriptions of implementing a compiler. See the related papers: Whetstone Algol Revisited, and The Whetstone KDF9 Algol Translator by Brian Randell
• Edsger W. Dijkstra, Algol 60 translation: an Algol 60 translator for the x1 and making a translator for Algol 60, report MR 35/61. Mathematisch Centrum, Amsterdam, 1961.<ref>{{

1. if: {{#if: http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF | {{#if: Archived copy |1}}}}

 ||Error on call to Template:cite web: Parameters url and title must be specified

}}{{

1. if:

 | {{#if: {{#if: | {{#if:  |1}}}}
   ||Error on call to template:cite web: Parameters archiveurl and archivedate must be both specified or both omitted

}} }}{{#if:

 | {{#if: 
   | [[{{{authorlink}}}|{{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | {{{author}}}
   }}]]
   | {{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | {{{author}}}
   }}
 }}

}}{{#if:

 | {{#if: | ; {{{coauthors}}} }}

}}{{#if: |

   {{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 |}}

}}{{#if:

 | . }}{{
 #if: 
 |  {{{editor}}}: 

}}{{#if:

   | {{#if:  | {{#if: Archived copy | [{{{archiveurl}}} Archived copy] }}}}
   | {{#if: http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF | {{#if: Archived copy | Archived copy }}}}

}}{{#if: | ({{{language}}}) }}{{#if:

 |  ()

}}{{#if:

 | . {{{work}}}

}}{{#if:

 |  {{{pages}}}

}}{{#if:

 | . {{{publisher}}}{{#if: 
   | 
   | {{#if:  || }}
 }}

}}{{#if:

 ||{{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 }}

}}.{{#if:

 |  Archived from the original on [[{{{archivedate}}}]].

}}{{#if:

 |  Retrieved on {{#time:Y F j|{{{accessdate}}}{{#if:  | , {{{accessyear}}}}}}}.

}}{{#if:

 |  Retrieved on {{{accessmonthday}}}, {{{accessyear}}}.

}}{{#if:

 |  Retrieved on {{{accessdaymonth}}} {{{accessyear}}}.

}}{{#if:

 |  “{{{quote}}}”

}}</ref>

Description: Algol 60 introduced block structure.

===The next 700 programming languages<ref name=Pierce2004>{{

1. if: {{#if: | {{#if: Great works in programming languages |1}}}}

 ||Error on call to Template:cite web: Parameters url and title must be specified

}}{{

1. if:

 | {{#if: {{#if: | {{#if:  |1}}}}
   ||Error on call to template:cite web: Parameters archiveurl and archivedate must be both specified or both omitted

}} }}{{#if: Pierce

 | {{#if: 
   | [[{{{authorlink}}}|{{#if: Pierce
     | Pierce{{#if: Benjamin C. | , Benjamin C. }}
     | {{{author}}}
   }}]]
   | {{#if: Pierce
     | Pierce{{#if: Benjamin C. | , Benjamin C. }}
     | {{{author}}}
   }}
 }}

}}{{#if: Pierce

 | {{#if: | ; {{{coauthors}}} }}

}}{{#if: Pierce|

   {{#if: 
   |  ({{{date}}})
   | {{#if: 2004
     | {{#if: 
       |  ({{{month}}} 2004)
       |  (2004)
     }}
   }}
 |}}

}}{{#if: Pierce

 | . }}{{
 #if: 
 |  {{{editor}}}: 

}}{{#if:

   | {{#if:  | {{#if: Great works in programming languages | [{{{archiveurl}}} Great works in programming languages] }}}}
   | {{#if:  | {{#if: Great works in programming languages | [{{{url}}} Great works in programming languages] }}}}

}}{{#if: | ({{{language}}}) }}{{#if:

 |  ()

}}{{#if:

 | . {{{work}}}

}}{{#if:

 |  {{{pages}}}

}}{{#if: Penn Engineering

 | . Penn Engineering{{#if: Pierce
   | 
   | {{#if: 2004 || }}
 }}

}}{{#if: Pierce

 ||{{#if: 
   |  ({{{date}}})
   | {{#if: 2004
     | {{#if: 
       |  ({{{month}}} 2004)
       |  (2004)
     }}
   }}
 }}

}}.{{#if:

 |  Archived from [{{{url}}} the original] on [[{{{archivedate}}}]].

}}{{#if:

 |  Retrieved on {{#time:Y F j|{{{accessdate}}}{{#if:  | , {{{accessyear}}}}}}}.

}}{{#if:

 |  Retrieved on {{{accessmonthday}}}, {{{accessyear}}}.

}}{{#if:

 |  Retrieved on {{{accessdaymonth}}} {{{accessyear}}}.

}}{{#if:

 |  “{{{quote}}}”

}}</ref>===

• Peter Landin
• Communications of the ACM 9(3):157–65, March 1966<ref>{{

1. if: {{#if: https://scholar.google.com/scholar?hl=uk&lr=&cluster=2856797924573721037&um=1&ie=UTF-8&sa=X&oi=science_links&resnum=1&ct=sl-allversions | {{#if: Google Академія |1}}}}

 ||Error on call to Template:cite web: Parameters url and title must be specified

}}{{

1. if:

 | {{#if: {{#if: | {{#if:  |1}}}}
   ||Error on call to template:cite web: Parameters archiveurl and archivedate must be both specified or both omitted

}} }}{{#if:

 | {{#if: 
   | [[{{{authorlink}}}|{{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | {{{author}}}
   }}]]
   | {{#if: 
     | {{{last}}}{{#if:  | , {{{first}}} }}
     | {{{author}}}
   }}
 }}

}}{{#if:

 | {{#if: | ; {{{coauthors}}} }}

}}{{#if: |

   {{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 |}}

}}{{#if:

 | . }}{{
 #if: 
 |  {{{editor}}}: 

}}{{#if:

   | {{#if:  | {{#if: Google Академія | [{{{archiveurl}}} Google Академія] }}}}
   | {{#if: https://scholar.google.com/scholar?hl=uk&lr=&cluster=2856797924573721037&um=1&ie=UTF-8&sa=X&oi=science_links&resnum=1&ct=sl-allversions | {{#if: Google Академія | Google Академія }}}}

}}{{#if: | ({{{language}}}) }}{{#if:

 |  ()

}}{{#if:

 | . {{{work}}}

}}{{#if:

 |  {{{pages}}}

}}{{#if:

 | . {{{publisher}}}{{#if: 
   | 
   | {{#if:  || }}
 }}

}}{{#if:

 ||{{#if: 
   |  ({{{date}}})
   | {{#if: 
     | {{#if: 
       |  ({{{month}}} {{{year}}})
       |  ({{{year}}})
     }}
   }}
 }}

}}.{{#if:

 |  Archived from the original on [[{{{archivedate}}}]].

}}{{#if:

 |  Retrieved on {{#time:Y F j|{{{accessdate}}}{{#if:  | , {{{accessyear}}}}}}}.

}}{{#if:

 |  Retrieved on {{{accessmonthday}}}, {{{accessyear}}}.

}}{{#if:

 |  Retrieved on {{{accessdaymonth}}} {{{accessyear}}}.

}}{{#if:

 |  “{{{quote}}}”

}}</ref>

Description: This seminal paper proposed an ideal language ISWIM, which without being ever implemented influenced the whole later development.

Fundamental Concepts in Programming Languages

• Christopher Strachey
• pdf

Description: Fundamental Concepts in Programming Languages introduced much programming language terminology still in use today, including R-values, L-values, parametric polymorphism, and ad hoc polymorphism.

Lambda Papers

• Gerald Jay Sussman and Guy L. Steele, Jr.
• AI Memos, 1975–1980
• Links to pdf's

Description: This series of papers and reports first defined the influential Scheme programming language and questioned the prevailing practices in programming language design, employing lambda calculus extensively to model programming language concepts and guide efficient implementation without sacrificing expressive power.

Structure and Interpretation of Computer Programs

Main article{{#if:|s}}: Structure and Interpretation of Computer Programs{{#if:

 |{{#if:|, | and }}[[{{{2}}}|{{{2}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{3}}}|{{{3}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{4}}}|{{{4}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{5}}}|{{{5}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{6}}}|{{{6}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{7}}}|{{{7}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{8}}}|{{{8}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{9}}}|{{{9}}}]]}}{{#if:

|, and [[{{{10}}}|{{{10}}}]]}}{{#if: | (too many parameters in {{main}})}}

 |{{#if:|, | and }}[[{{{2}}}|{{{2}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{3}}}|{{{3}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{4}}}|{{{4}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{5}}}|{{{5}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{6}}}|{{{6}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{7}}}|{{{7}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{8}}}|{{{8}}}]]}}{{#if:
 |{{#if:|, |, and }}[[{{{9}}}|{{{9}}}]]}}{{#if: