Hagit Attiya and Jennifer L Welch: “Sequential Consistency versus Linearizability,” ACM Transactions on Computer Systems (TOCS), volume 12, number 2, pages 91–122, May 1994.
An often-cited constraint on distributed database design is the CAP theorem, an impossibility result in distributed systems. It states that in a linearizable database, if the network is interrupted, some nodes cannot respond to requests. Although being able to tolerate network faults is important, the performance and response times of a database are often even more important, and CAP says nothing about those. It's also a pretty boring theorem.
Attiya and Welch's paper, which we'll discuss in this session, is vastly more interesting. It also proves an impossibility result, but it's about response times: on a network where the uncertainty of packet delay is u, there is no algorithm that implements linearizability with read requests faster than u/4 and write requests faster than u/2. On a network where packet delay is highly variable (like many computer networks), a linearizable database is therefore inevitably going to be slow.
The paper then goes on to compare linearizability to sequential consistency (a weaker consistency guarantee), and shows that sequential consistency can be significantly faster.
This is a theoretical paper, but its applications to practical systems are very real. Its proofs are elegant and not too difficult to follow. It was almost a decade ahead of the CAP theorem. And moreover, it has no male co-authors. What's not to love about it?
Martin Kleppmann is author of the O'Reilly book Designing Data-Intensive Applications (http://dataintensive.net (http://dataintensive.net/)), which analyses the data infrastructure and architecture used by internet companies. He previously co-founded a startup, Rapportive, that was acquired by LinkedIn in 2012. His technical blog is at http://martin.kleppmann.com (http://martin.kleppmann.com/) and he's @martinkl (https://twitter.com/martinkl) on Twitter.