Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What's the best paper you've read in 2020?

news.ycombinator.com

Post reply on HN
Print view View original

61–70 of 197 posts

Re: Ask HN: What's the best paper you've read in 2020?

#61

Post by abecedarius »

lacker wrote: post #54

Attention Is All You Need https://arxiv.org/abs/1706.03762 It's from 2017 but I first read it this year. This is the paper that defined the "transformer" architecture for deep neural nets. Over the past few years, transformers have become a more and more common architecture, most notably with GPT-3 but also in other domains besides text generation. The fundamental principle behind the transformer is that it can detec…

It's clearly important but I found that paper hard to follow. The discussion in AIMA 4th edition was clearer. (Is there an even better explanation somewhere?)

Re: Ask HN: What's the best paper you've read in 2020?

#62

Post by imglorp »

Keeping CALM: When Distributed Consistency Is Easy

In computing theory, when do you actually need coordination to get consistency? They partition the space into two kinds of algorithm, and show that only one kinds needs coordination.

CACM, 9/2020. https://cacm.acm.org/magazines/2020/9/246941-keeping-calm/fu...

Re: Ask HN: What's the best paper you've read in 2020?

#64

Post by luizfelberti »

evmar wrote: post #7
luizfelberti wrote: post #2

For 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…

The Google File System (GFS) paper from 2003 mentions erasure codes. Which isn't to say they did it then, but rather that the technique of using erasure coding was known back then. (And surely before GFS too, I just picked it as an example of a large data storage system that used replication and a direct predecessor to the systems you mentioned.) https://static.googleusercontent.com/media/research.google.c...

CDs (remember those? lol) also implemented Reed-Solomon erasure codes for the stored data, erasure codes in storage systems aren't new at all, and that's not what this paper is about.

I actually found out about this paper because it was referenced in a slide presentation from Google about Colossus (which is the successor to GFS). GFS indeed uses erasure coding with a 1.5x factor, but erasure coding alone does not guarantee durability, and thus needs to be combined with replication to satisfy that requirement, and erasure coding is not the same thing as replication.

The innovation here is explicitly the combination of a new erasure coding algorithm (LRC) AND replication, with a combined storage amplification that is much lower than the previous SOTA.

The paper explicitly compares the new algorithm (LRC) with GFS and other alternatives, and explains why it's better, so this is really not something that is comparable to the 2003 GFS paper in any way (or to any other prior art really), as this is not just a trivial application of erasure coding in a storage system.

There's also this paper [0] from 2001 which digs a bit deeper into the Erasure Codes vs Replication idea that I can recommend if you're interested

[0] http://fireless.cs.cornell.edu/publications/erasure_iptps.pd...

Re: Ask HN: What's the best paper you've read in 2020?

#65

Post by luizfelberti »

jeffbee wrote: post #8
luizfelberti wrote: post #2

For 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…

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 gave a longer explanation in a sibing comment to yours [1]

[0] http://fireless.cs.cornell.edu/publications/erasure_iptps.pd...

[1] https://news.ycombinator.com/item?id=25351678

Re: Ask HN: What's the best paper you've read in 2020?

#66

Post by 6gvONxR4sf7o »

abecedarius wrote: post #61
lacker wrote: post #54

Attention Is All You Need https://arxiv.org/abs/1706.03762 It's from 2017 but I first read it this year. This is the paper that defined the "transformer" architecture for deep neural nets. Over the past few years, transformers have become a more and more common architecture, most notably with GPT-3 but also in other domains besides text generation. The fundamental principle behind the transformer is that it can detec…

It's clearly important but I found that paper hard to follow. The discussion in AIMA 4th edition was clearer. (Is there an even better explanation somewhere?)

It's crazy to me to see what still feel like new developments (come on, it was just 2017!) making their way into mainstream general purpose undergraduate textbooks like AIMA. It's this what getting old feels like? :-\

I start to understand what you always hear from older ICs about having to work to keep up, or else every undergrad coming out will know things you don't.

Re: Ask HN: What's the best paper you've read in 2020?

#67

Post by specialist »

tgb wrote: post #29

Here'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?

Re: Ask HN: What's the best paper you've read in 2020?

#68

Post by luizfelberti »

H8crilA wrote: post #13
luizfelberti wrote: post #2

For 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…

The primary reason why you should be using 3x or higher replication is the read throughput (which makes it only really relevant for magnetic storage). If the data is replicated 1.6x then there's only 1.6 magnetic disk heads per each file byte. If you replicate it 6x then there's 6 magnetic disk heads for each byte. At ~15x it becomes cheaper to store in SSD with ~1.5x reed-solomon/erasure code overhead since SSD has…

Everything you just said is on point, but I think that's an orthogonal thing to what the paper is going for. Hot data should absolutely have a fully-materialized copy at the node where operations are made, and an arbitrary number of readable copies can be materialized for added performance in systems that don't rely on strong consistency as much.

However for cold-data, there really hasn't been (or at least I am unaware of) any system that can achieve the combined durability of 1.5x Reed-Solomon codes + 3x replication, with such a small penalty to storage costs.

Like you said though, it's definitely not the thing you'd be doing for things that prioritize performance as aggressively as the use-cases you've suggested.

Re: Ask HN: What's the best paper you've read in 2020?

#70

Post by ricksunny »

https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7062204/

Chen, Y.W.; Yiu, C.B.; Wong, K.Y. Prediction of the SARS-CoV-2 (2019-nCoV) 3C-like protease (3CL (pro)) structure: Virtual screening reveals velpatasvir, ledipasvir, and other drug repurposing candidates. F1000Research 2020, 9, 129.

This paper (based on a machine learning-driven open source drug docking tool from Scripps Institute) from Feb/Mar formed the basis for the agriceutical venture I started for supporting pandemic management in Africa. We’re in late stage trialing talks with research institutes here in East Africa.

https://www.emske-phytochem.com

Post reply on HN