back
13 comments
Anything written by Leslie Lamport is worth the effort.

Time, Clocks and the Ordering of Events in a Distributed System (seminal paper which won various awards): http://research.microsoft.com/en-us/um/people/lamport/pubs/p...

That link actually takes you to a complete list of Lamport's works.

I wish I could upvote twice. Lamport's writing is _very_ accessible ( at least to this college dropout ) and I really enjoyed reading Time, Clocks and the Ordering of Events. Paxos Made Simple is another favorite: http://research.microsoft.com/en-us/um/people/lamport/pubs/p....
This is a great list. I would add:

* The stable marriage problem (D. Gale and L. S. Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.), http://en.wikipedia.org/wiki/Stable_marriage_problem

* Knuth's Dancing Links algorithm http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...

"A tutorial on Hidden Markov Models and selected applications in speech recognition" (by Lawrence Rabiner) - blew me away.

link: http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tuto...

I'll also add "Design and Implementation of the Sun Network Filesystem" (by Sandberg et al.) - fantastic read.

Brewer's CAP Theorem

The first link is the paper which constituted the proof of the theorem, the other two provide more context and background.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.... http://en.wikipedia.org/wiki/CAP_theorem http://www.julianbrowne.com/article/viewer/brewers-cap-theor...

There is one set of papers that applies to multi-areas...information Theory

Paper and Journal article list is here: http://en.wikipedia.org/wiki/Information_theory

Its one of the most important theories of the modern science age of the 19th/20th century

Shannon's original paper is still a surprisingly good read: http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pd...
Seconded; imo this paper is a pretty good introduction to the basic concepts and motivations of information theory even today. Impressive for a 63-year-old paper.
If you want a reminder of what a stud Shannon was, remember that his masters thesis (A Symbolic Analysis of Relay and Switching Circuits) proved that you could use boolean algebra and boolean arithmetic to analyze the circuits and relays used in the telephone networks at the time. It then went one step further and proved that the inverse was also true, you could use relays and switches to perform boolean logic operations -- this was the key insight that made digital electronics possible. Not too bad for work that did not even get him a Ph.D. :)
Someone once called information theory the 'physics' of computation. I am inclined to agree wholeheartedly.
Something on quantum computation like, Shor's algorithm: http://arxiv.org/abs/quant-ph/0010034
That's already there. Did you read the linked item?
Ouch. Really sorry about that. Wish i could delete it. I would also add any paper by David Deutsch on quantum communication like this: http://xxx.lanl.gov/pdf/quant-ph/9906007v2