I've read five of of the seven papers on the list. The two I haven't read are Cerf and Kahn's, and Berner-Lee's.
Turing's paper on computability was particularly hard to follow, for me, because he used these gothic-font upper-chase characters to name all sorts of objects, and all those characters looked kinda the same to me! I had to use auxiliary materials to be able to make my way through the paper. Today, I would recommend reading it with Charles Petzold's easy-to-follow book on the paper: https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
Cook's paper on NP-completeness was also hard to follow (again, for me). As with Turing's paper, I had to use auxiliary materials to make my way. Today, I would recommend reading instead an introductory book on computational complexity that works through Cook's proof.
Shannon's paper is a work of art, clearly articulated and beautifully written. It's just not casual reading, to put it mildly.
Brin and Page's paper, and Codd's paper, are not hard to follow, at least as I remember them, but understanding Brin and Page's work requires some knowledge of Linear Algebra.
Where does the Brin-and-Page paper require linear algebra? It mentions "eigenvector" once, in a tangential remark. The "simple iterative algorithm" is how you find the fixed point of any contraction mapping, linear or not. Knowing that it is also an eigenvector is just a distraction -- you aren't going to use Gaussian elimination, not if you know what is good for you.
Yes, but the paper blathers on and on in prose about history and related work and goals and future work. It might only mention eigenvector once in a tangential remark, but that remark is like 80% of the algorithm content of the paper.
It doesn't require linear algebra to understand the paper or how the algorithm works, but it does require linear algebra to understand why the algorithm works. In general, since the induced 1-norm of a stochastic matrix S is exactly equal to 1 but not smaller than 1, the mapping x↦Sx is NOT a contraction. Neither convergence of the power method nor uniqueness of fixed point are guaranteed. (If there are multiple fixed points, there are multiple inconsistent rankings.)
In the paper, the significance of the so-called "damping factor" is not clear. However, with linear algebra, we know that the damping factor makes the stochastic matrix positive rather than merely nonnegative. Hence the Perron eigenvalue is "simple" (i.e. of multiplicity one), the Perron vector is unique and the power iteration must converge to it.
That's easier explained using fixed-point theory: The damping factor makes the mapping x↦Sx into an actual contraction (on the space of probability distributions). Not to mention that it has a simple common-sense justification (you don't want to get stuck in a subnetwork that only links to itself, or drown out a subnetwork that has more outlinks than inlinks).
There is probably some gain from understanding the algorithm specifically as a Markov chain iteration (if nothing else, it provides a great example for Markov chain iteration), but I think it's perfectly possible -- and easier -- to understand it as a fixed-point iteration on a compact space. And I am someone who does algebra for a living and normally explains everything algebraically if ever possible...
Ha, me too! When the first title included Entscheidungsproblem I thought this would be intellectual edgelording. But, this is a legit list.
Of course, you can't do justice to the entire field with such a short list. Two papers on web but none on graphics, e.g. But it's a fine reading list for sure.
We have Shannon's "Communication Theory of Secrecy Systems" as arguably the beginning of modern cryptography and then Diffie & Hellman's "New Directions in Cryptography" which first introduced public-key cryptography.
It would be interesting to see the opposite of this; which papers are really interesting and look useful, but did not end up having a significant impact?
I'm not so sure. In my (under-read) mental model, blockchain takes you from fail-stop fault-tolerance (a la Paxos) to Byzantine fault-tolerance, i.e. how do you compute in a massively distributed system when no node has any reason to trust any other node.
BTC is just combining all the past research into an application, which has it's own place but sadly not here. You might wanna read this [0] for all the past ideas that satoshi took
I would add "On the Criteria to Be Used in Decomposing Systems into Modules" (1972, ~7800 citations) by Parnas, though more software engineering than computer science in a strict sense.
Does anyone actually use Paxos in real life? And let me ask the same question for all other academic distributed algorithms right away. I recall seeing a study some 10 years ago checking the major cloud providers for Byzantine fault tolerance and finding none of them to exhibit the qualities that the known algorithms would guarantee; apparently they would just rely on timing and hoping things don't get too twisted.
Yes, if you’re using any sort of multi master db, you’re using a variant of paxos, raft or something which you shouldn’t really trust until aphyr blasts it into the low earth orbit.
The paper itself is very approachable and worth spending an hour or so on.
I remember trying to read the paper and giving up somewhere early in the proof. I certainly don't think it gives a great intuition why the algorithm holds, so "approachability" is a matter of definition (does it tell a fun story? sure yeah).
Yes, it's very widely used at Google through Chubby, which underpins many core pieces of infrastructure, including name resolution. (It used to be common practice to depend more directly on Chubby for synchronization of state via shared global files, but that fell out of favor about 6 years ago due to reliability risks associated with just blasting out changes globally without any canarying.)
> I recall seeing a study some 10 years ago checking the major cloud providers for Byzantine fault tolerance and finding none of them to exhibit the qualities that the known algorithms would guarantee.
I'm curious which study you're referring to. I could believe that while Paxos might be used as a building block, it might not be used in a consistent manner throughout.
Also, note that not all of the variations of Paxos handle Byzantine faults.
If this is up your alley, Ideas That Created the Future[1] has like 40 more, decent introductions to their ideas, and provides a sort of thematic throughline from Aristotle to the modern computer science.
Oh man, if you think Shannon's A Mathematical Theory of Communication is his most foundational contribution to computer science, you haven't seen his master's thesis from a decade prior.
I would also add J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression", 1977 [1]. LZ (Lempel-Ziv) is the foundation of many data compression algorithms that are still in use today.
I actually found this to be an odd mix. Are we selecting papers that had an influence on computer science (as in, the theory of computation), or that had an impact on technology? Or are we just using CS as a catch-all for "all things computer"?
The Turing paper is foundational for CS, but without it, would the technology have evolved differently? Probably not. Most software engineers have not read it. Conversely, the IP standard is a technological cornerstone, but there's hardly any science in it. It's just a specification of a fairly simple protocol that you need to know when doing almost anything network-adjacent.
Something doesn't feel quite right to me seeing the PageRank paper in a short list alongside Turing and Shannon's foundational work on computability and information theory. “On Computable Numbers, with an Application to the Entscheidungsproblem” is almost 90 years old at this point and just as true and relevant now as it was then. Is PageRank even as relevant today as it was in 1998, let alone another 50 years from now?
I wonder how pagerank was influential to CS as a field?
even mapreduce is more a rally clever technique than a boundary pushing or boundary identifying extension of the field. unlike, say, CSP --- which is missing in the list.
still unlike the conciseness and structure of the list. it could evolve into a nice book :-D
My understanding of the term "history of CS" would be "how CS evolved", as a field. How do we think about "processing 'data' with computers". what can we compute? what are limitations in how fast we can compute? how to we talk about and present algorithms, prescriptions for these computations? how do we talk about data and how we structure it (leading to SQL, and sgml/xml/JSON)?
Pagerank in contrast is a very specific type of breakthrough, a breakthrough for it's application domain. But it's not a breakthrough for how we compute or how we think about computation.
We can’t estimate what will be relevant 50 years from now.
If quantum or biological computing find some success, none of these are going to be relevant.
That said, pagerank is important to understand the modern tech world. Search is something we take for granted, and it’s great there’s a deeply mathematical (and somewhat counterintuitive) theory behind it.
The big insight of the PageRank paper is that you can use MC integration to approximate PR, not PR itself. Hence making the problem much easier to distribute.
> He sketches out a hypothetical “Turing Machine,” proving that, if something is computable at all, a machine (in principle) can handle it.
That's not what Turing proved. Instead, what he proved in his paper was that there are some problems which aren't solvable by Turing Machines (and therefore presumably by any machine). That's the Entscheidungsproblem (decision problem) referenced in the title.
What TFA references is the so-called Church-Turing-Thesis, which is exactly that, a thesis. It can't really be proven although we have very strong reason to believe it given that in almost 100 years nobody has found a system of computation more powerful than Turing Machines.
And in 100 years we have gone completely the opposite direction in terms of where we think artificial intelligence lies. Rather than constructing a machine with all the known truths, modern searching for artificial intelligence using machines is mostly sifting through human commentary to create an organized feuilleton machine versus Leibniz's axiomatic approach
No, Turing had precisely that approach of feeding the machine with learning material in mind[1], but you have to build a machine apt to consume generic knowledge body before you throw at it anything.
There have also been attempts to canonicalize knowledge on the web (semantic web) and lots of things inside of computers are in fact deterministic.
But that is not the direction that AI seems to be taking, it is "smart" because it does a good job of parroting humans that sound "smart", not because it "knows" truths.
I beleive you are wrong that "nobody has found a system of computation more powerful than Turing Machines". A turing machine can not perform indeterminacy, however, the actor model can.
I read that sentiment here a few years ago but couldn't get anything more out of it than actors can race, but a turing machine is determistic. I could very well have it wrong.
If you were computing with actors, and you also had a sufficiently-detailed spec about the actor model, is there some particular algorithm you could not compute by just executing a TLA+ spec of your actor algorithm using Turing-ish software?
Non-deterministic Turing machines [1] are the standard way to define Non-deterministic complexity classes like NP or NEXP, so there are definitely Turing machines with indeterminacy.
Communicating Sequential Processes (Hoare),
The Next 700 Programming Languages (Landin),
As We May Think (Bush),
Can Programming Be Liberated from the von Neumann Style (Backus)
And this seems to be a cool course: https://canvas.harvard.edu/courses/34992/assignments/syllabu...
> This course examines papers every computer scientist should have read, from the 1930s to the present. It is meant to be a synthesizing experience for advanced students in computer science: a way for them to see the field as a whole, not through a survey, but by reliving the experience of its creation. The idea is to create a unified view of the field of computer science, for students who already know something about it, by replaying its entire evolution at an accelerated frame rate.
I'd argue both as well as McCulloch & Pitts. Maybe Boltzmann or Rummelhart (Backprop) as well. Honestly, I wouldn't know where to stop, there are so many cool papers.
Yeah. But before AlexNet GPUs were only for graphics and esoteric papers in scientific computing. The realization that conv layers map well to cuda cores has led to GPU production being a national security issue.
I think any list like this has to include:
"Time, clocks, and the ordering of events in a distributed system" By Lamport also, in almost any networked system having strict ordering is fantastically useful. And of course how could we also forget "The Byzantine generals problem".
113 comments
[ 3.1 ms ] story [ 175 ms ] threadI've read five of of the seven papers on the list. The two I haven't read are Cerf and Kahn's, and Berner-Lee's.
Turing's paper on computability was particularly hard to follow, for me, because he used these gothic-font upper-chase characters to name all sorts of objects, and all those characters looked kinda the same to me! I had to use auxiliary materials to be able to make my way through the paper. Today, I would recommend reading it with Charles Petzold's easy-to-follow book on the paper: https://www.amazon.com/Annotated-Turing-Through-Historic-Com...
Cook's paper on NP-completeness was also hard to follow (again, for me). As with Turing's paper, I had to use auxiliary materials to make my way. Today, I would recommend reading instead an introductory book on computational complexity that works through Cook's proof.
Shannon's paper is a work of art, clearly articulated and beautifully written. It's just not casual reading, to put it mildly.
Brin and Page's paper, and Codd's paper, are not hard to follow, at least as I remember them, but understanding Brin and Page's work requires some knowledge of Linear Algebra.
Thank you for sharing this on HN.
I don't known if anyone has gone through the trouble to re-typeset the original paper in LaTex.
In the paper, the significance of the so-called "damping factor" is not clear. However, with linear algebra, we know that the damping factor makes the stochastic matrix positive rather than merely nonnegative. Hence the Perron eigenvalue is "simple" (i.e. of multiplicity one), the Perron vector is unique and the power iteration must converge to it.
There is probably some gain from understanding the algorithm specifically as a Markov chain iteration (if nothing else, it provides a great example for Markov chain iteration), but I think it's perfectly possible -- and easier -- to understand it as a fixed-point iteration on a compact space. And I am someone who does algebra for a living and normally explains everything algebraically if ever possible...
Of course, you can't do justice to the entire field with such a short list. Two papers on web but none on graphics, e.g. But it's a fine reading list for sure.
[1] https://en.wikipedia.org/wiki/Turing_Award
[2] https://en.wikipedia.org/wiki/G%C3%B6del_Prize
[0] - https://queue.acm.org/detail.cfm?id=3136559
J. Cooley and J. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” 1965
I would add "On the Criteria to Be Used in Decomposing Systems into Modules" (1972, ~7800 citations) by Parnas, though more software engineering than computer science in a strict sense.
Probably just needs to be a bigger list.
Unix paper.
Hinton on deep learning (pick one).
Map Reduce + GFS from Google.
Paxos from dist systems.
PGP paper; RSA paper
Surprised no one has mentioned The Unreasonable Effectiveness of Data. Data is more important than complex domain specific algorithms.
The paper itself is very approachable and worth spending an hour or so on.
Yes, it's very widely used at Google through Chubby, which underpins many core pieces of infrastructure, including name resolution. (It used to be common practice to depend more directly on Chubby for synchronization of state via shared global files, but that fell out of favor about 6 years ago due to reliability risks associated with just blasting out changes globally without any canarying.)
https://en.wikipedia.org/wiki/Paxos_(computer_science)#Produ... lists a bunch of other use cases (notably, Google's Spanner and Amazon's DynamoDB).
> And let me ask the same question for all other academic distributed algorithms right away.
Raft (designed as a more understandable alternative to Paxos) is more commonly used, as I understand it.
https://en.wikipedia.org/wiki/Raft_(algorithm)#Production_us...
> I recall seeing a study some 10 years ago checking the major cloud providers for Byzantine fault tolerance and finding none of them to exhibit the qualities that the known algorithms would guarantee.
I'm curious which study you're referring to. I could believe that while Paxos might be used as a building block, it might not be used in a consistent manner throughout.
Also, note that not all of the variations of Paxos handle Byzantine faults.
I can't find the study any more, though I'm pretty sure I saw it on HN...
Plan9+CSP.
Both, maybe, polar opposites, but complementary.
[1]: https://mitpress.mit.edu/9780262045308/ideas-that-created-th...
https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_a...
He outlined how you could use switching elements in circuits (read: transistors) to define boolean logic.
(That's not to downplay the importance of, well, establishing the foundations of the entire field of information theory.)
Bitcoin paper is really interesting from CS perspective
And also had HUGE influence on the world
And no, I dont own btc
Hewitt, Carl; Bishop, Peter; Steiger, Richard (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI.
https://www.ijcai.org/Proceedings/73/Papers/027B.pdf
[1] https://courses.cs.duke.edu/spring03/cps296.5/papers/ziv_lem...
The Turing paper is foundational for CS, but without it, would the technology have evolved differently? Probably not. Most software engineers have not read it. Conversely, the IP standard is a technological cornerstone, but there's hardly any science in it. It's just a specification of a fairly simple protocol that you need to know when doing almost anything network-adjacent.
I wonder how pagerank was influential to CS as a field?
even mapreduce is more a rally clever technique than a boundary pushing or boundary identifying extension of the field. unlike, say, CSP --- which is missing in the list.
still unlike the conciseness and structure of the list. it could evolve into a nice book :-D
Agreed about map reduce though.
My understanding of the term "history of CS" would be "how CS evolved", as a field. How do we think about "processing 'data' with computers". what can we compute? what are limitations in how fast we can compute? how to we talk about and present algorithms, prescriptions for these computations? how do we talk about data and how we structure it (leading to SQL, and sgml/xml/JSON)?
Pagerank in contrast is a very specific type of breakthrough, a breakthrough for it's application domain. But it's not a breakthrough for how we compute or how we think about computation.
does that make sense?
What joke of a list :-)
If quantum or biological computing find some success, none of these are going to be relevant.
That said, pagerank is important to understand the modern tech world. Search is something we take for granted, and it’s great there’s a deeply mathematical (and somewhat counterintuitive) theory behind it.
But, indirectly looking, it influenced establishment of Google, which influenced many thousands of innovations in this field.
So yes, PageRank is hugely influential in my opinion.
We don't use cuneiform these days, but back in its day, it was as close to a standard writing system as it was possible to get.
I was actually doing something similar on my own, so I might recommend some papers
- RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978)
- PageRank: The PageRank Citation Ranking: Bringing Order to the Web (1999)
- MapReduce: MapReduce: simplified data processing on large clusters (2008)
- Bitcoin: Bitcoin: A Peer-to-Peer Electronic Cash System (2008)
- BackProp: Learning representations by back-propagating errors (1986)
- Hoare Logic: An Axiomatic Basis for Computer Programming (1969)
I think the also ran list should be in the main list.
That's not what Turing proved. Instead, what he proved in his paper was that there are some problems which aren't solvable by Turing Machines (and therefore presumably by any machine). That's the Entscheidungsproblem (decision problem) referenced in the title.
What TFA references is the so-called Church-Turing-Thesis, which is exactly that, a thesis. It can't really be proven although we have very strong reason to believe it given that in almost 100 years nobody has found a system of computation more powerful than Turing Machines.
https://philsci-archive.pitt.edu/9085/1/SterrettBringingUpTu...
But that is not the direction that AI seems to be taking, it is "smart" because it does a good job of parroting humans that sound "smart", not because it "knows" truths.
The actor model is a way to describe that a program exists, not if it’s possible to ‘compute’ that program.
You’re right that it can describe more things than a Turing machine, but doesn’t provide a constructive way to compute them.
If you were computing with actors, and you also had a sufficiently-detailed spec about the actor model, is there some particular algorithm you could not compute by just executing a TLA+ spec of your actor algorithm using Turing-ish software?
[1] https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...
"Sketchpad: A Man-machine Graphical Communication System."
And this seems to be a cool course: https://canvas.harvard.edu/courses/34992/assignments/syllabu... > This course examines papers every computer scientist should have read, from the 1930s to the present. It is meant to be a synthesizing experience for advanced students in computer science: a way for them to see the field as a whole, not through a survey, but by reliving the experience of its creation. The idea is to create a unified view of the field of computer science, for students who already know something about it, by replaying its entire evolution at an accelerated frame rate.
Andrew Tridgell and Paul Mackerras, The rsync algorithm, June 1996, https://www.andrew.cmu.edu/course/15-749/READINGS/required/c...