Papers

Papers every engineer should read

Widely read papers on module boundaries, why software stays hard, trusting your tools, floating point, remote calls and the hidden cost of machine learning in production, for engineers in any field.

6 papers · 6 h 0/6

  1. On the Criteria To Be Used in Decomposing Systems into Modules(opens in a new tab)

    Parnas 1972 Communications of the ACM 30 min

    Information hiding: start from the design decisions that are difficult or likely to change, and give each module one of them to hide, instead of making each step of a flowchart a module. Two decompositions of the same keyword-in-context (KWIC) index program show the difference.

  2. No Silver Bullet: Essence and Accidents of Software Engineering(opens in a new tab)

    Brooks 1987 IEEE Computer 45 min

    Brooks separates the essential difficulty of software, which comes from the problem a program must solve, from the accidental difficulty of expressing it with current tools. Because high-level languages and time-sharing had already removed much of the accidental part, he argues that no single technique would improve productivity tenfold within a decade.

  3. Reflections on Trusting Trust(opens in a new tab)

    Thompson 1984 Communications of the ACM 20 min

    Thompson's Turing Award lecture describes a C compiler changed to insert a backdoor into the login program and to reinsert both changes whenever it compiles a clean copy of its own source, so the attack survives with no trace in any source file.

  4. What Every Computer Scientist Should Know About Floating-Point Arithmetic(opens in a new tab)

    Goldberg 1991 ACM Computing Surveys 180 min

    A tutorial on IEEE 754 floating point: how results are rounded, how relative error and units in the last place measure the rounding, why subtracting nearly equal numbers loses accuracy, and what guard digits, infinities, NaNs and denormalized numbers are for.

  5. A Note on Distributed Computing(opens in a new tab)

    Waldo et al. 1997 Mobile Object Systems, LNCS 1222 40 min

    An argument that a remote call cannot be made to look like a local one, because distribution adds latency, a separate memory space, concurrency and partial failure, and a local interface has no way to express them. It first appeared as a Sun Microsystems Laboratories report in 1994.

  6. Hidden Technical Debt in Machine Learning Systems(opens in a new tab)

    Sculley et al. 2015 NeurIPS 2015 40 min

    The maintenance costs an ML system builds up outside its model code: entangled features (changing anything changes everything), hidden feedback loops, undeclared consumers of predictions, unstable data dependencies, glue code, pipeline jungles and configuration. Its best-known figure draws the model code as a small box inside the serving, data and monitoring infrastructure around it.

Algorithms and data structures in real systems

The shortest-path and ranking algorithms, indexes, hashing schemes, sketches and columnar layouts inside maps, search engines, databases and storage services, for engineers who choose or tune them and students who want to see where these structures are used.

10 papers · 11.5 h 0/10

  1. A Note on Two Problems in Connexion with Graphs(opens in a new tab)

    Dijkstra 1959 Numerische Mathematik 20 min

    The shortest-path algorithm that grows a set of nodes whose distance from the source is final, always adding the nearest remaining node. The first of the two problems is the minimum spanning tree, solved by the method now usually credited to Prim and Jarník.

  2. The Ubiquitous B-Tree(opens in a new tab)

    Comer 1979 ACM Computing Surveys 60 min

    A survey of B-trees and their variants, including the B+-tree, which keeps every key in the leaves and links the leaves left to right for sequential scans. It explains why a shallow, wide tree suits storage where each node read costs one disk access.

  3. Skip Lists: A Probabilistic Alternative to Balanced Trees(opens in a new tab)

    Pugh 1990 Communications of the ACM 40 min

    Skip lists: sorted linked lists with extra express levels chosen by coin flips, giving expected O(log n) search, insertion and deletion with no rebalancing code.

  4. The Log-Structured Merge-Tree (LSM-Tree)(opens in a new tab)

    O'Neil et al. 1996 Acta Informatica 120 min

    The LSM-tree: collect index updates in a memory component and merge them into larger sorted components on disk in batches, so random index writes become sequential disk I/O.

  5. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web(opens in a new tab)

    Karger et al. 1997 STOC 1997 60 min

    Consistent hashing: hash each cache to several random points and each item to one point in the same unit interval, then assign the item to the closest cache point, so adding or removing a cache moves only the items near its points. With hash mod n, changing n moves almost every item.

  6. The Anatomy of a Large-Scale Hypertextual Web Search Engine(opens in a new tab)

    Brin and Page 1998 Computer Networks and ISDN Systems 60 min

    The design of the first Google prototype: crawler, inverted index, link-based ranking with PageRank, and the storage layout behind a database of at least 24 million pages.

  7. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm(opens in a new tab)

    Flajolet et al. 2007 AofA 2007 120 min

    HyperLogLog: hash each item, use the first bits to pick a register, and keep the longest run of leading zeros seen in each register. A harmonic mean over the registers estimates counts well beyond a billion with about 2 percent error in 1.5 kilobytes.

  8. An Improved Data Stream Summary: The Count-Min Sketch and its Applications(opens in a new tab)

    Cormode and Muthukrishnan 2005 Journal of Algorithms 75 min

    The Count-Min sketch: a small grid of counters, one hash function per row, that estimates how often each item appeared in a stream, with error bounded by a fraction of the total count.

  9. C-Store: A Column-oriented DBMS(opens in a new tab)

    Stonebraker et al. 2005 VLDB 2005 75 min

    C-Store, a read-optimized database that stores each column separately, keeps overlapping projections of a table sorted on different columns, compresses each column, and takes new writes in a small writeable store that a tuple mover merges into the read-optimized store.

  10. Dremel: Interactive Analysis of Web-Scale Datasets(opens in a new tab)

    Melnik et al. 2010 VLDB 2010 60 min

    A columnar format for nested records that encodes their structure with repetition and definition levels, combined with a multi-level serving tree that runs aggregation queries over trillion-row tables in seconds.