Unix shell command languages by Ken Thompson
Ask HN: What's the best paper you've read in 2020?
71–80 of 197 posts
Re: Ask HN: What's the best paper you've read in 2020?
#72Here's a wonderful one I read a little over a year ago: "Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush" https://arxiv.org/abs/1511.07428 https://www.pnas.org/content/113/47/13283 It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that tha…
Nice. My math-fu is very weak. I dimly recall a notion for estimating the number of unfound bugs for a code base. Is this similar?
Yeah, exactly. If you wanted to know that your code was bug free, how could you do it? Set a team of experts to each independently scour for bugs. But when do you stop? The quick answer is that you should keep going until every bug you've found, has been found at least twice. I think of this as being that you "just barely" found a bug if only one person identified it, so there are probably still bugs you have "just barely" not found remaining.
Re: Ask HN: What's the best paper you've read in 2020?
#73Earlier quoted context omitted.
I think for the major players you mentioned the 2016 paper was retrospective. Everyone was already doing it. Even mid-tier players like Dropbox Magic Pocket were using erasure coding by 2016, and their scheme was mostly written by ex-Google engineers influenced by Colossus.
Oh I am absolutely aware that erasure codes are an old thing, Reed-Solomon codes exist since the 1960's, but this is not simply a trivial application of erasure coding to a storage system: erasure codes alone don't provide the same durability guarantees that replication does. [0] This is a combination of erasure coding AND replication, whose combined storage amplification is dramatically lower than previous SOTA. I g…
Thanks for the clarification. I still think these techniques were somewhat widespread already ... see for example this figure from US Patent 9292389 describing nested, aka layered coding that to my thinking is isomorphic with the "LRC" or "pyramid code" described by the Microsoft researchers.
By the way, not at all trying to say this paper isn't interesting. I keep it in my filing cabinet to show my colleagues when I need to describe this technique, since Google hasn't ever bothered to describe Colossus in a way I can reference.
Re: Ask HN: What's the best paper you've read in 2020?
#74Earlier quoted context omitted.
Nice. My math-fu is very weak. I dimly recall a notion for estimating the number of unfound bugs for a code base. Is this similar?
Yeah, exactly. If you wanted to know that your code was bug free, how could you do it? Set a team of experts to each independently scour for bugs. But when do you stop? The quick answer is that you should keep going until every bug you've found, has been found at least twice. I think of this as being that you "just barely" found a bug if only one person identified it, so there are probably still bugs you have "just b…
Is that a direct application of the paper or something else? (sorry I didn't read it)
Just wondering because this rule of thumb sounds intuitively wrong to me. Depending on the difficulty of the bugs and the skill levels of the experts, it seems possible for them to find every "easy" bug at least twice while having none of them finding the hardest bug even once. (real world example would be some obscure zero-day security bug)
Re: Ask HN: What's the best paper you've read in 2020?
#751) The original MapReduce paper https://static.googleusercontent.com/media/research.google.c...
2) Snowflake and its tiered storage, among other things http://pages.cs.wisc.edu/~yxy/cs839-s20/papers/snowflake.pdf
Re: Ask HN: What's the best paper you've read in 2020?
#76Earlier quoted context omitted.
Yeah, exactly. If you wanted to know that your code was bug free, how could you do it? Set a team of experts to each independently scour for bugs. But when do you stop? The quick answer is that you should keep going until every bug you've found, has been found at least twice. I think of this as being that you "just barely" found a bug if only one person identified it, so there are probably still bugs you have "just b…
Is that a direct application of the paper or something else? (sorry I didn't read it) Just wondering because this rule of thumb sounds intuitively wrong to me. Depending on the difficulty of the bugs and the skill levels of the experts, it seems possible for them to find every "easy" bug at least twice while having none of them finding the hardest bug even once. (real world example would be some obscure zero-day secu…
agreed, I thought of the same issue. Seems like there has to be some assumption about even difficulty of finding bugs / catching species of birds
Re: Ask HN: What's the best paper you've read in 2020?
#77Here's a wonderful one I read a little over a year ago: "Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush" https://arxiv.org/abs/1511.07428 https://www.pnas.org/content/113/47/13283 It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that tha…
Is it similar to the german tank problem?
Re: Ask HN: What's the best paper you've read in 2020?
#78Here's a wonderful one I read a little over a year ago: "Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush" https://arxiv.org/abs/1511.07428 https://www.pnas.org/content/113/47/13283 It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that tha…
> But mostly I just love the name. Apparently PNAS had them change it for the final publication, sadly.
Big game from an organization with that acronym.
Re: Ask HN: What's the best paper you've read in 2020?
#79Out of topic, but could you suggest a good resource for papers? I am interested in software mostly
Re: Ask HN: What's the best paper you've read in 2020?
#80For me, it was "Erasure Coding in Windows Azure Storage" from Microsoft Research (2016) [0] The idea that you can achieve the same practical effect of a 3x replication factor in a distributed system, but only increasing the cost of data storage by 1.6x, by leveraging some clever information theory tricks is mind bending to me. If you're operating a large Ceph cluster, or you're Google/Amazon/Microsoft and you're runn…
Erasure coding was already used in storage tapes in 1985.
> some clever information theory tricks is mind bending to me
It's a pretty trivial first-degree linear function, y = ax + b