Design 19: Ideas from Notable Computer Papers

Theme

A lot of concepts in computer science become common knowledge because they are so fundamental to the field. They are often easy to explain and understand after the fact, especially because of the number of educational resources available.

This can make it easy to underappreciate the iteration and human effort required to come up with those ideas before they became accepted knowledge. I think this is especially true for topics like shortest paths, sorting, hashing, and other algorithms that now feel basic or obvious.

This puzzle steps back and looks at notable research papers where some influential ideas first appeared.

Grid

The answers that most heavily influenced the grid shape during construction were Diffie-Hellman, Lamport clock, and Bloom filter. I then slotted the remaining answers around that initial shape.

I also only used the first half of Byzantine Generals, Relational Model, and Actor Model as answers. The full names were too long to fit in the grid or make for a good typing experience.

Something I've become more cognizant of is creating more down answers. It's easy to find intersections by stacking across answers together, but having more distinct down answers makes the grid feel more balanced and visually appealing. I think I'll continue to bias toward more down answers in future puzzles.

Clues

I wanted to include the names of the corresponding research papers in every clue because it fit the theme of the puzzle. There were a few answers where I couldn't do that, such as RSA, Actor Model, and Quicksort, either because of limited space or because it would spoil the answer. Some paper titles were also quite long and used a decent chunk of the allotted 150-character limit. When I started running out of room, I used phrases like "from the ___ paper" instead of "introduced in the ___ paper" or removed articles like "a" and "the."

Since I only used the first half of Byzantine Generals, Relational Model, and Actor Model as answers, I had to make sure the clues used the first half as a fill-in-the-blank and the second half as context.

Originally, the paper titles weren't quoted, which caused them to blend into the rest of the text. I updated the clues to quote the paper titles to make it more visually distinctive, but this pushed some clues over the character limit, so I had to simplify their wording.

Tradeoffs

I think this puzzle is more difficult than my other puzzles because the answers are not concentrated in a single subfield. Instead, the clues span areas like algorithms, distributed systems, and cryptography. As a result, the puzzle is broader in scope but also asks for very specific knowledge, which is a difficult ask. The common thread across the answers is that these ideas became foundational within their respective subfields and originated in influential research papers.

Notes

There were many notable papers from the 2000s by Google and Amazon, such as MapReduce, Bigtable, Spanner, and Dynamo, that I didn't include. Since the puzzle already contained several distributed systems papers, I didn't want large-scale systems research from big tech to be overrepresented. Google's 2017 Transformer paper was the exception because its influence extends well beyond distributed systems. It serves as the foundation for modern LLMs and fundamentally changed neural network architectures for sequence modeling.

The 2014 Raft paper was included because it builds on the 1989 Paxos paper by emphasizing understandability and practical implementation. It has since become one of the standard ways distributed consensus is taught.

I also didn't want the puzzle to have too much recency bias, so Raft and Transformer are the only papers from the last two decades that I included.