List of publications in computer science

Encyclopedia : L : LI : LIS : List of publications in computer science

---

This is a list of important publications in computer science, organized by field.

Some reasons why a particular publication might be regarded as important:

• Topic creator – A publication that created a new topic
• Breakthrough – A publication that changed scientific knowledge significantly
• Introduction – A publication that is a good introduction or survey of a topic
• Influence – A publication which has significantly influenced the world
• Latest and greatest – The current most advanced result in a topic

''On computable numbers, with an application to the

• Alan Turing
• Proceedings of the London Mathematical Society, Series 2, 42 (submitted May 28 1936, read November 12 1936), pp 230–265. Errata appeared in Series 2, 43 (1937), pp 544–546.
• [Online version (MS IExplorer only)]
• [PDF version of above page (verified to display properly with xpdf and acroread)]

Description: This article set the limits of computer science. It defined the Turing Machine, a model for all computations. On the other hand it proved the undecidability of the halting problem and Entscheidungsproblem and by doing so found the limits of possible computation.

Importance: Topic creator, Breakthrough, Influence

On certain formal properties of grammars

• Noam Chomsky
• Information and Control 2 (1959), 137–167.

Description: This article introduced what is now known as the Chomsky hierarchy, a containment hierarchy of classes of formal grammars that generate formal languages.

Importance: Topic creator, Breakthrough, Influence

Finite automata and their decision problem

• Michael O. Rabin and Dana S. Scott
• IBM J. Research and Development, 3:114–125, 1959.
• [Online version]

Description: Mathematical treatment of automata, proof of core properties, and definition of non-deterministic finite automaton

Importance: Topic creator, Breakthrough, Influence, Introduction

Introduction to Automata Theory, Languages, and Computation

• John E. Hopcroft
• Jeffrey D. Ullman
• Addison-Wesley, 1979, ISBN 0-201-02988-X

Description: A popular textbook.

Importance: Introduction

Computability: An introduction to recursive function theory

• Nigel J. Cutland
• Cambridge University Press, 1980, ISBN 0-521-29465-7

Description: A popular textbook.

Importance: Introduction

On the computational complexity of algorithms

• Juris Hartmanis
• Richard Stearns
• Trans. Amer. Math. Soc. 117 (1965), 285–306.

Description: This paper gave computational complexity its name and seed.

Importance: Topic creator, Breakthrough, Influence

The complexity of theorem proving procedures

• S. A. Cook
• Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (1971), pp. 151–158.

Description: This paper introduced the concept of NP-Completeness and proved that Boolean satisfiability problem(SAT) is NP-Complete.

Importance: Topic creator, Breakthrough, Influence

Reducibility among combinatorial problems

• R. M. Karp
• In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum Press, New York, NY, 1972.

Description: This paper showed that 21 different problems are NP-Complete and showed the importance of the concept.

Importance: Influence

Computers and Intractability: A Guide to the Theory of NP-Completeness

• Michael R. Garey, David S. Johnson
• Freeman, New York, 1979
• ISBN 0716710455

Description: The main importance of this book is due to its extensive list of more than 300 NP-Complete problems. This list became a common reference and definition. It is important to note that though the book was published only few years after the concept was defined such an extensive list was found.

Importance: Introduction, Influence, Latest and greatest

''Theory and Applications of

• Andrew Chi-Chih Yao
• Proc. 23rd Symposium on the Foundations of Computer Science (1982), pp. 80–91

Description: This paper introduced the concept of Trapdoor functions and described some of its application, like in cryptography.

Importance: Topic creator, Breakthrough

The Knowledge Complexity of Interactive Proof Systems

• Shafi Goldwasser, Silvio Micali, Charles Rackoff
• SIAM Journal of Computing, 18(1):186–208, February 1989.

Description: This paper introduced the concept of zero knowledge.

Importance: Topic creator, Breakthrough

How to Construct Random Functions

• Oded Goldreich, Shafi Goldwasser, Silvio Micali
• Journal of the ACM, 33(4), 1984, 792–807.
• [Online copy (PDF)]

Description: This paper showed that the existence of one way functions leads to computational randomness.

Importance: Topic creator, Breakthrough, Latest and greatest, Influence

''

• Adi Shamir
• Journal of the ACM, 39(4):869–877, 1992.

Description: IP is a complexity class whose characterization is quite different from the usual time/space bounded computational classes. In this paper Shamir showed the IP = PSPACE, hence each problem in one complexity class is solvable in the other.

Importance: Breakthrough

Interactive Proofs and the Hardness of Approximating Cliques

• Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy
• Journal of the ACM, 43:268–292, 1996.

• Sanjeev Arora and Shmuel Safra
• Journal of the ACM, 45:70–122, 1998.

Proof Verification and the Hardness of Approximation Problems

• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy
• Journal of the ACM, 45:501–555, 1998.

Description: These three papers established the surprising fact that certain problems in NP remain hard even when only an approximative solution is required.

Importance: Topic creator, Breakthrough, Influence

''

• C.H. Papadimitriou
• Addison-Wesley, 1994. ISBN 0201530821

Description: This book provides a very good introduction to Computational Complexity

Importance: Introduction

''A machine program for

• M. Davis, G. Logemann, D. Loveland
• Communications of the ACM, 5:394–397, 1962.

Description: The DLL algorithm. The basic algorithm for SAT and other NP-Complete problems.

Importance: Breakthrough, Influence

A Machine-Oriented Logic Based on the Resolution Principle

• J. Alan Robinson
• Communications of the ACM, 5:23–41, 1965.

Description: First description of resolution and unification used in theorem proving; used in Prolog & logic programming.

Importance: Topic Creator, Breakthrough, Influence

Optimization by simulated annealing

• Kirkpatrick, S., Gelatt, C., & Vecchi, M.
• Science, Number 4598, 13, pages 671–680, May 1983.
• [Online copy]

Description: This article described simulated annealing which is now a very common heuristic for NP-Complete problems.

Importance: Influence

''

• Donald Knuth

Description: This monograph has three popular algorithms books and a number of fascicles. The algorithms are written in both English and MIX assembly language (or MMIX assembly language in more recent fascicles). This makes algorithms both understandable and precise. However, the use of a low-level programming language frustrates some programmers more familiar with modern structured programming languages.

Importance: Influence

''

• Thomas H. Cormen
• Charles E. Leiserson
• Ronald L. Rivest
• Clifford Stein
• MIT Press and McGraw-Hill. 2nd Edition, 2001. 1st Edition (with first three authors) published in 1991.

Description: As its name indicates this textbook is a very good introduction to algorithms. This book became so popular that it is almost the de facto standard for basic algorithms teaching.

Importance: Introduction, Influence

How to Solve It By Computer

• RG Dromey
• Prentice Hall (1982), ISBN 0134340019

Description: Explains the Whys of algorithms and data-structures. Explains the Creative Process, the Line of Reasoning, the Design Factors behind innovative solutions.

Importance: Introduction

See Also: How to Solve It

The Design and Analysis of Computer Algorithms

• Alfred V. Aho
• John E. Hopcroft
• Jeffrey D. Ullman
• Addison-Wesley, 1974, ISBN 0-201-00029-6

Description: One of the standard texts on algorithms for the period of approximately 1975–1985.

Importance: Influence, Introduction

Algorithms

• Robert Sedgewick
• Addison-Wesley, 1983, ISBN 0-201-06672-6

Description: A very popular text on algorithms in the late 1980s. It was more accessible and readable (but more elementary) than Aho, Hopcroft, and Ullman. There are more recent editions.

Importance: Influence

''Algorithms + Data Structures

• Niklaus Wirth
• Prentice Hall, 1976, ISBN 0-13-022418-9

Description: An early, influential book on algorithms and data structures, with implementations in Pascal.

Importance: Influence

A formal theory of inductive inference

• Ray Solomonoff
• Information and Control, vol. 7, pp. 1–22, March 1964; pp. 224–254, June 1964.

Description: This was the beginning of Algorithmic information theory and Kolmogorov complexity. Note that though Kolmogorov complexity is named after Andrey Kolmogorov, he said that the seeds of that idea are due to Ray Solomonoff. Andrey Kolmogorov contributed a lot to this area but in later articles.

Importance: Topic creator, Breakthrough, Influence

Algorithmic information theory

• Gregory Chaitin
• IBM Journal of Research and Development 21 (1977), pp. 350–359, 496.
• [Online version]

Description: A good introduction to Algorithmic information theory by one of the important people in the area.

Importance: Introduction

''

• C.E. Shannon
• Bell System Technical Journal, 27:379–423,623–656, 1948
• [Online copy (HTML)]

Description: This paper created communication theory and information theory.

Importance: Topic creator, Breakthrough, Introduction, Influence

Error detecting and error correcting codes

• Richard Hamming
• Bell Systems Technical Journal, vol. 29, pp. 147–160, 1950
• [Online copy]

Description: In this paper, Hamming introduced the idea of error-correcting code. He created the Hamming code and the Hamming distance and developed methods for code optimality proofs.

Importance: Topic creator, Breakthrough, Introduction, Influence

A Method for the Construction of Minimum Redundancy Codes

• David A. Huffman
• Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Number 9, pp. 1098–1101.
• [Online copy]

Description: The Huffman coding.

Importance: Influence, Breakthrough

A Universal Algorithm for Sequential Data Compression

• Jacob Ziv
• Abraham Lempel
• IEEE Transactions on Information Theory, Vol. 23, No. 3, pp. 337–343.
• [Online copy]

Description: The LZ77 compression algorithm.

Importance: Influence, Breakthrough

Elements of Information Theory

• Thomas M. Cover
• Joy A. Thomas
• Wiley, 1991.

Description: A good and popular introduction to information theory.

Importance: Influence, Introduction

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.

Importance: Influence

'' The

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

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.

Importance: Influence, Breakthrough

Operating Systems: Design and implementation

• Andrew S. Tanenbaum
• Prentice Hall, 1987

Description: Theoretical as well as practical textbook of the operating systems, with Minix as the example. The book is often referred to as the Minix bible, as it includes the full source.

Importance: Breakthrough, Influence

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

Importance: Influence

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.

Importance: Topic creator, Breakthrough, Influence

The Entity Relationship Model – Towards a Unified View of Data

• P.P-S. 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.

Importance: Breakthrough, Influence

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.

Importance: Topic creator, Introduction, Influence

Principles of Transaction-Oriented Database Recovery

• Theo Härder, Andreas Reuter
• ACM Computing Surveys 15(4), May 1983

Description: Introduced the ACID-Paradigma for transactions.

Importance: Topic creator, Introduction, Influence

''

• C.E. Shannon
• " Communication Theory of Secrecy Systems", Bell System Technical Journal, vol.28-4, page 656–715, 1949.
• [Online copy (PDF)]

Description: Information theory based analysis of cryptography.

Importance: Breakthrough, Introduction, Influence

New directions in cryptography

• W.Diffie, M.E.Hellman
• IEEE Transactions on Information Theory, IT-22, 6, 1976, pp. 644–654
• [Online copy (HTML)]

Description: This paper suggested public key cryptography and presented Diffie-Hellman key exchange.

Importance: Topic creator, Breakthrough, Introduction, Influence, Latest and greatest (A great paper from every perspective...)

A Method for Obtaining Digital Signatures and Public Key Cryptosystems

• R. Rivest, A. Shamir, L. Adleman
• Communications of the ACM, Vol. 21 (2), 1978, pages 120–126
• [Online copy (HTML)]

Description: The RSA encryption method. The first public key encryption method.

Importance: Breakthrough, Influence

How to Share a Secret

• Shamir, A.
• Communications of the ACM, vol. 22, no. 11, pp. 612–613 (November 1979)
• [Online copy (HTML)]

Description: A safe method for sharing a secret.

Importance: Topic creator, Breakthrough

How to Prove all NP-Statements in Zero-Knowledge, and a Methodology of Cryptographic Protocol Design

• Goldreich, O, Micali, S., Wigderson, A.
• CRYPTO, LNCS vol 263, pp. 171–185, 1987
• [Online copy(HTML)]

Description: This paper explains how to construct a zero-knowledge proof system for any language in NP.

Importance: Breakthrough, Influence

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority

• Goldreich, O, Micali, S., Wigderson, A.
• STOC, pgs. 218-229, 1987
• [Online copy(HTML)]

Description: Seminal paper in secure function evaluation

Importance: Breakthrough, Influence

Computing machinery and intelligence

• Alan Turing
• Mind, 59:433–460, 1950.
• [Online copy]

Description: This paper discusses whether machine can think and suggested the Turing test as a method for checking it. In a sense, this was the beginning of artificial intelligence

Importance: Topic creator, Breakthrough, Influence

A Proposal for the Dartmouth Summer Research Project on Artificial Intelligence

• John McCarthy
• Marvin Minsky
• N. Rochester
• C.E. Shannon
• [Online copy]

Description: This summer research proposal marks the areas of research in artificial intelligence since then. It was a very long summer.

Importance: Influence

Fuzzy sets

• Lotfi Zadeh
• Information and Control, Vol. 8, pp. 338-353. (1965).
• [Online copy]

Description: The seminal paper published in 1965 provides details on the mathematics of fuzzy set theory.

Importance: Topic creator, Influence

Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference

• Judea Pearl
• ISBN: 1558604790 Publisher: Morgan Kaufmann Pub, 1988

Description: This book introduced Bayesian methods to AI.

Importance: Topic creator, Influence

• Stuart J. Russell and Peter Norvig
• Prentice Hall, Englewood Cliffs, New Jersey, 1995, ISBN 0130803022
• [Textbook's website]

Description: The standard textbook in Artificial Intelligence. The authors claim that it used in over 900 colleges and universities in 89 countries.

Importance: Introduction, Influence

Unformatted list of reading considered as seminal works in the field of artificial intelligence

• Gödel, Escher, Bach : An Eternal Golden Braid by Douglas R. Hofstadter
• Understanding Understanding: Essays on Cybernetics and Cognition by Heinz von Foerster
• In the Image of the Brain: Breaking the Barrier Between Human Mind and Intelligent Machines by Jim Jubak
• Today's Computers, Intelligent Machines and Our Future by Hans Moravec, Stanford University
• The Society of Mind by Marvin Minsky, ISBN 0671657135 15 March 1998
• by Marvin Minsky and Seymour Papert ISBN 0262631113 28 December 1987
• by HP Newquist ISBN 0672304120.
• by Hubert L. Dreyfus ISBN 0262041340.

• [TechBookReport AI] Reviews of books on machine learning and AI, and related application fields such as data mining.

''

• E. M. Gold
• Information and Control, 10:447–474, 1967
• [Online version(HTML)]

Description: This paper created Algorithmic learning theory.

Importance: Topic creator, Breakthrough, Influence

On the uniform convergence of relative frequencies of events to their probabilities

• V. Vapnik, A. Chervonenkis
• Theory of Probability and its Applications, 16(2):264--280, 1971

Description: Computational learning theory, VC theory, statistical uniform convergence and the VC dimension.

Importance: Breakthrough, Influence

A theory of the learnable

• Leslie Valiant
• Communications of the ACM, 27(11):1134–1142 (1984)

Description: The Probably approximately correct learning (PAC learning) framework.

Importance: Topic creator, Breakthrough, Influence

Learnability and the Vapnik-Chervonenkis dimension

• A. Blumer
• A. Ehrenfeucht
• D. Haussler
• M. K. Warmuth
• Journal of the ACM, 36(4):929–965, 1989.

Description: The complete characterization of PAC learnability using the VC dimension.

Importance: Breakthrough, Influence

Cryptographic limitations on learning boolean formulae and finite automata

• M. Kearns
• L. G. Valiant
• In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433–444, New York. ACM.
• [Online version(HTML)]

Description: Proving negative results for PAC learning.

Importance: Influence

The strength of weak learnability

• Robert E. Schapire
• Machine Learning, 5(2):197–227, 1990.
• [Online version(HTML)]

Description: Proving that weak and strong learnability are equivalent in the noise free PAC framework.

Importance: Breakthrough, Influence

Learning in the presence of malicious errors

• Michael Kearns
• Ming Li
• Journal on Computing, 22(4):807–837, August 1993.
• [Online version(HTML)]

Description: Proving possibility and imposibility result in the malicious errors framework.

Importance: Breakthrough, Influence

'' The

• C.D. Kuglin and D.C. Hines
• IEEE 1975 Conference on Cybernetics and Society, 1975, New York, pp. 163–165, September

Description: A correlation method based upon the inverse Fourier transform

Importance: Influence

'' An Iterative

• Lucas, B.D. and Kanade, T.
• Proceedings of the 7th International Joint Conference on Artificial Intelligence, 674–679,Vancouver, Canada,1981
• [Online version]

Description: This paper provides efficient technique for image registration

Importance: Influence

The Laplacian Pyramid as a compact image code

• Peter J. Burt and Edward H. Adelson
• IEEE Transactions on Communications, volume = "COM-31,4", pp. 532–540, 1983.
• [Online version]

Description: A technique for image encoding using local operators of many scales

Importance: Influence

Snakes: Active contour models

• Michael Kass, Andrew Witkin, and Demetri Terzopoulos
• International Journal of Computer Vision, 1(4):321–331, 1988. (Marr Prize Special Issue)
• [Online version]

Description: An interactive variational technique for image segmentation and visual tracking

Importance: Influence, topic creator

''

• M. Isard and A. Blake
• International Journal of Computer Vision, 29(1):5–28, 1998.
• [Online version]

Description: A technique for visual tracking

Importance: Influence

On the translation of languages from left to right

• D. E. Knuth
• Information and Control 8 (1965), 607-639.

Description: Bottom up parsing for deterministic context-free languages from which later the LALR approach of Yacc developed.

Importance: Breakthrough, Influence

Semantics of Context-Free Languages.

• D.E. Knuth
• Math. Systems Theory 2:2 (1968), 127-145.

Description: About grammar attribution, the base for yacc's s-attributed and zyacc's LR-attributed approach.

Importance: Breakthrough, Influence

YACC: Yet another compiler-compiler

• Stephen C. Johnson
• Unix Programmer's Manual Vol 2b, 1979
• [Online copy (HTML)]

Description: Yacc is a tool that made compiler writing much easier.

Importance: Influence

Compilers: Principles, Techniques and Tools

• Alfred V. Aho
• Ravi Sethi
• Jeffrey D. Ullman
• Addison-Wesley, 1986. ISBN 0201100886

Description: This book became a classic in compiler writing. It is also known as the Dragon book, after the (red) dragon that appears on its cover.

Importance: Introduction, Influence

Assigning meanings to programs

• Robert W. Floyd
• Mathematical Aspects of Computer Science, pages 19–32, 1967

Description: Introduced the idea of attaching logical assertions to points in a program in order to prove its correctness and influenced C. A. R. Hoare's seminal work on program verification.

Importance: Topic creator, Breakthrough, Influence, Introduction

An axiomatic basis for computer programming

• C. Antony R. Hoare
• Communications of the ACM, 12:576–580, 1969

Description: Axiomatic foundation for program correctness proofs was laid. The importance of the use of formal methods is explained.

Importance: Topic creator, Breakthrough, Influence, Introduction

The temporal logic of programs

• Amir Pnueli
• In Proc. 18th IEEE Symposium on Foundation of Computer Science, pages 46–57, 1977.

Description: The use of temporal logic was suggested as a method for formal verification.

Importance: Topic creator, Influence

Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints

• Patrick and Radhia Cousot
• In Proc. 4th ACM Symposium on Principles of Programming Languages, 238–252, 1977

Description: Introducing abstract interpretation for the verification of computer programs by sound approximations.

Importance: Topic creator, Influence.

Model Checking

• Edmund M. Clarke, Orna Grumberg, Doron A. Peled
• MIT Press, 1999

Description: An overview of Model checking, an automatic formal verification technique

Importance: Introduction

History of Computation

The Computer from Pascal to von Neumann

• Herman H. Goldstine
• Princton University Press, 1972, ISBN 0-691-08104-2

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

Importance:

A History of Computing in the Twentieth Century

edited by:

• Nicholas Metropolis
• J. Howlett
• Gian-Carlo Rota
• Academic Press, 1980, ISBN 0-12-491650-3

Description: Several chapters by pioneers of computing.

Importance:

''

• Peter Naur, Brian Randell (eds.)
• Garmisch, Germany, 7–11 October 1968, Brussels, Scientific Affairs Division, NATO (1969) 231pp.
• [Online copy (PDF)]

Description: Conference of leading figures in software field circa 1968

Importance: Defined the field of Software engineering

''

• Dijkstra, E. W.
• Communications of the ACM, 11(3):147–148, March 1968
• [Online copy (HTML)]

Description: Don't use goto – the beginning of structured programming.

Importance: Topic creator, Influence

On the criteria to be used in decomposing systems into modules

• David Parnas
• Communications of the ACM, December:1053–1058, December 1972.
• [Online copy (HTML)]

Description: The importance of modularization and information hiding.

Importance: Influence

''

• Brooks, Jr., F. P.
• Addison Wesley Professional. 2nd edition, 1995.

Description: Throwing more people at the task will not speed its completion...

Importance: Influence

''

• Brooks, Jr., F. P.
• Computer, 20(4):10–19, April 1987
• [Online copy (HTML)]

Description: We will keep having problems with software...

Importance: Influence

''

• Raymond, E.S.
• First Monday, 3, 3 (March 1998)
• [Online copy (HTML)]

Description: Open source methodology.

Importance: Influence

''

• E. Gamma, R. Helm, R. Johnson, J. Vlissides
• Addison-Wesley, Reading, Massachusetts, 1995.

Description: This book was the first to define and list design patterns in computer science

Importance: Topic creator, Influence

The Structure of \"THE\"-Multiprogramming System

• Dijkstra, E. W.
• Communication of the ACM, Vol. 11, No. 5 May 1968, pp. 345–346
• [Online copy (HTML)]

Description: The introduction of basic primitives like mutex as the basis of multiprocessing programming.

Importance: Breakthrough, Influence

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

• Leslie Lamport
• IEEE Transactions on Computers, volume C-28, number 9, pp. 690–691, September 1979.

Description: Requirements that guarantee the correct execution of multi process programs were defined.

Importance: Breakthrough, Influence

LogP: Towards a realistic model of parallel computation

• D. Culler, R. Karp, D. Patterson, A. Sahay, K. E. Schauser, E. Santos, R. Subramonian, and T. von Eicken
• In Proceedings 4th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May 1993.
• [Online version]

Description: The LogP framework for parallel computing was suggested. The LogP provided a way to bridge the gap between theoretical analysis of algorithm and building real world systems.

Importance: Influence

Ethernet: Distributed packet switching for local computer networks

• R.M. Metcalfe, D.R. Boggs
• Communications of the ACM 19, 7 (July 1976), 395–404
• [Online copy (HTML)]

Description: The Ethernet protocol.

Importance: Influence, Latest and greatest

A Dynamic Network Architecture

• Sean W. O'Malley, Larry L. Peterson
• ACM Transactions on Computer Systems, 10(2), May 1992
• [Online copy]

Description: Network software in distributed systems.

Importance: Influence

Computer Networks

• Andrew S. Tanenbaum
• Prentice Hall, mid '80s

Description: Textbook description of all network standards at the time. In 2005, it is in its fourth edition (published in 2002), include all current networking technology.

Importance: Influence

The Byzantine Generals Problem

• Leslie Lamport, Robert Shostak, Marshall Pease
• Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press
• [Online version]

Description: Impossibility result for distributed computing, see Byzantine failure.

Importance: Influence, Breakthrough

'Impossibility of Distributed Consensus with One Faulty process''

• Michael J. Fischer, Nancy Lynch, Michael S. Paterson
• [Online version]

Description: Impossibility to achieve consensus in asynchronous systems if one process is faulty .

Importance: Influence, Breakthrough

See also

• List of publications in science
• Notable publications in software engineering
• List of open problems in computer science
• DBLP (Digital Bibliography & Library Project)
• The Collection of Computer Science Bibliographies
• The Complexity of Songs

External links

• [Most cited articles in Computer Science]

Academic Search Engines

• [Google Scholar]
• [CiteSeer]

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?