Time, Clocks, and the Ordering of Events (Lamport, 1978)
The paper that introduced logical clocks. Published in CACM (1978). Annotated reading at https://semicolony.dev/papers/time-clocks/.
Semicolony — Annotated CS papers
Foundational distributed-systems, storage, and networking papers, read closely and annotated. TL;DR, problem statement, contributions, criticisms, where the ideas show up today.
Latest posts
The Byzantine Generals Problem (Lamport, Shostak, Pease, 1982)
The threat model behind every blockchain consensus algorithm. Published in ACM TOPLAS (1982). Annotated reading at https://semicolony.dev/papers/byzantine-generals/.
Paxos Made Simple (Lamport, 2001)
The 13-page plain-English rewrite of the 1989 Paxos paper. Published in SIGACT News (2001). Annotated reading at https://semicolony.dev/papers/paxos-made-simple/.
In Search of an Understandable Consensus Algorithm (Ongaro & Ousterhout, 2014)
Designed to be easier to teach than Paxos. Powers etcd, Consul, CockroachDB. Published in USENIX ATC (2014). Annotated reading at https://semicolony.dev/papers/raft/.
Dynamo · Amazon's Highly Available Key-value Store (DeCandia et al, 2007)
Consistent hashing, vector clocks, eventual consistency in one paper. Published in SOSP (2007). Annotated reading at https://semicolony.dev/papers/dynamo/.
Bigtable · A Distributed Storage System for Structured Data (Chang et al, 2006)
The blueprint for HBase, Cassandra, and a generation of wide-column stores. Published in OSDI (2006). Annotated reading at https://semicolony.dev/papers/bigtable/.
Spanner · Google's Globally Distributed Database (Corbett et al, 2012)
TrueTime + Paxos at planetary scale. Foundational for CockroachDB, Yugabyte. Published in OSDI (2012). Annotated reading at https://semicolony.dev/papers/spanner/.
Conflict-Free Replicated Data Types (Shapiro et al, 2011)
Strongly eventual consistency without coordination. Published in INRIA TR (2011). Annotated reading at https://semicolony.dev/papers/crdts/.
Impossibility of Distributed Consensus with One Faulty Process (Fischer, Lynch, Paterson, 1985)
The bound every consensus algorithm has to negotiate. Published in JACM (1985). Annotated reading at https://semicolony.dev/papers/flp/.
Building on Quicksand (Helland, 2009)
Why exactly-once delivery is a fiction and idempotency is the answer. Published in CIDR (2009). Annotated reading at https://semicolony.dev/papers/building-on-quicksand/.
The Log-Structured Merge-Tree (O'Neil et al, 1996)
Foundational for every modern KV store — RocksDB, LevelDB, Cassandra. Published in Acta Informatica (1996). Annotated reading at https://semicolony.dev/papers/lsm-tree/.
ARIES · A Transaction Recovery Method (Mohan et al, 1992)
How nearly every database implements crash recovery. Published in ACM TODS (1992). Annotated reading at https://semicolony.dev/papers/aries/.
A Critique of ANSI SQL Isolation Levels (Berenson, Gray et al, 1995)
Why standard isolation levels are fuzzy. Named snapshot isolation. Published in SIGMOD (1995). Annotated reading at https://semicolony.dev/papers/sql-isolation-critique/.
F1 · A Distributed SQL Database that Scales (Shute et al, 2013)
How Google replaced sharded MySQL on Spanner. Published in VLDB (2013). Annotated reading at https://semicolony.dev/papers/f1/.
Calvin · Fast Distributed Transactions for Partitioned Databases (Thomson et al, 2012)
Deterministic transaction ordering — an alternative to 2PC. Published in SIGMOD (2012). Annotated reading at https://semicolony.dev/papers/calvin/.
C-Store · A Column-Oriented DBMS (Stonebraker et al, 2005)
10× speedup on analytical workloads. Spawned Vertica, ClickHouse. Published in VLDB (2005). Annotated reading at https://semicolony.dev/papers/c-store/.
The Google File System (Ghemawat, Gobioff, Leung, 2003)
The blueprint for HDFS, Colossus, every "scale-out" filesystem since. Published in SOSP (2003). Annotated reading at https://semicolony.dev/papers/gfs/.
MapReduce · Simplified Data Processing on Large Clusters (Dean & Ghemawat, 2004)
The programming model that defined a decade of big-data systems. Published in OSDI (2004). Annotated reading at https://semicolony.dev/papers/mapreduce/.
The Tail at Scale (Dean & Barroso, 2013)
Why p99 matters more than averages. Published in CACM (2013). Annotated reading at https://semicolony.dev/papers/tail-at-scale/.
Borg, Omega, and Kubernetes (Burns et al, 2016)
The Google paper documenting the lineage from Borg to Omega to k8s. Published in ACM Queue (2016). Annotated reading at https://semicolony.dev/papers/borg-omega-kubernetes/.
End-to-End Arguments in System Design (Saltzer, Reed, Clark, 1984)
The architectural principle that shaped TCP/IP. Published in ACM TOCS (1984). Annotated reading at https://semicolony.dev/papers/end-to-end-arguments/.
Maglev · A Fast and Reliable Software Network Load Balancer (Eisenbud et al, 2016)
Google's consistent-hash L4 load balancer. Published in NSDI (2016). Annotated reading at https://semicolony.dev/papers/maglev/.
Practical Byzantine Fault Tolerance (Castro & Liskov, 1999)
The first BFT protocol practical enough for production. Published in OSDI (1999). Annotated reading at https://semicolony.dev/papers/pbft/.