Millions of tiny databases

March 4, 2020May 25, 2020 ~ Adrian Colyer ~ 12 Comments

Millions of tiny databases, Brooker et al., NSDI'20 This paper is a real joy to read. It takes you through the thinking processes and engineering practices behind the design of a key part of the control plane for AWS Elastic Block Storage (EBS): the Physalia database that stores configuration information. In the same spirit as ... Continue Reading

Seeing is believing: a client-centric specification of database isolation

August 29, 2017 ~ Adrian Colyer ~ Leave a comment

Seeing is believing: a client-centric specification of database isolation Crooks et al., PODC’17 This paper takes a fresh look at the issue of isolation levels, a topic we’ve looked at before and which contains quite a bit of complexity. The gold standard reference for understanding isolation is Adya’s Generalized isolation level definitions. Unlike the definitions ... Continue Reading

ACIDRain: concurrency-related attacks on database backed web applications

August 7, 2017 ~ Adrian Colyer ~ 5 Comments

ACIDRain: Concurrency-related attacks on database-backed web applications Warszawski & Bailis, SIGMOD'17 Welcome back to a new term of The Morning Paper. To kick things off, we have 'ACID Rain' - a terrific paper from SIGMOD'17 that pulls together a number of threads we've studied previously: transaction processing, anomalies, and security. What ACIDRain demonstrates is that ... Continue Reading

Hybrids on Steroids: SGX-based high-performance BFT

June 5, 2017 ~ Adrian Colyer ~ 1 Comment

Hybrids on Steroids: SGX-based high performance BFT Behl et al., EuroSys'17 Byzantine fault tolerance (BFT) is the kind of fault-tolerance designed to withstand not just process crashes and network problems, but also active adversaries trying to break the system, as well as storage and memory corruptions and so on. We've taken a look at BFT ... Continue Reading

Incremental consistency guarantees for replicated objects

January 13, 2017November 11, 2019 ~ Adrian Colyer ~ 3 Comments

Incremental consistency guarantees for replicated objects Guerraoui et al., OSDI 2016 We know that there's a price to be paid for strong consistency in terms of higher latencies and reduced throughput. We also know that there's a price to be paid for weaker consistency in terms of application correctness and / or programmer difficulty. Furthermore, ... Continue Reading

The many faces of consistency

January 12, 2017November 11, 2019 ~ Adrian Colyer ~ 7 Comments

The many faces of consistency Aguilera & Terry, IEEE TC on Data Engineering Bulletin, 2016 Update: Mark Vukolic posted a comment to point me to an ACM Survey paper he published together with Paolo Viotti last year that looks at 50 different consistency models for distributed non-transactional storage systems and puts them into a comprehensive ... Continue Reading

Just say NO to Paxos overhead: replacing consensus with network ordering

December 8, 2016November 11, 2019 ~ Adrian Colyer ~ 19 Comments

Just say NO to Paxos overhead: replacing consensus with network ordering Li et al., OSDI 2016 Everyone knows that consensus systems such as Paxos, Viewstamped Replication, and Raft impose high overhead and have limited throughput and scalability. Li et al. carefully examine the assumptions on which those systems are based, and finds out that within ... Continue Reading

The SNOW theorem and latency-optimal read-only transactions

December 6, 2016November 11, 2019 ~ Adrian Colyer ~ 3 Comments

The SNOW theorem and latency-optimal read-only transactions Lu et al., OSDI 2016 Consider a read-only workload (as in 100%). You can make that really fast - never any need to coordinate, never any need to invalidate any cached values… Now consider a write-only workload - you can make that even faster, if no-one’s ever going ... Continue Reading

The Honey Badger of BFT protocols

November 18, 2016November 11, 2019 ~ Adrian Colyer ~ 5 Comments

The Honey Badger of BFT Protocols Miller et al. CCS 2016 The surprising success of cryptocurrencies (blockchains) has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) protocols for mission critical applications, such as financial transactions. In a ‘traditional’ distributed system consensus algorithm setting we assume a relatively ... Continue Reading

The load, capacity, and availability of quorum systems

October 3, 2016November 11, 2019 ~ Adrian Colyer ~ 8 Comments

The load, capacity, and availability of quorum systems Naor & Wool, SIAM J Computing 1998 Update: fixed 'non-intersection property' to read 'non-empty intersection property.' Quite an important difference! With thanks to those who pointed out my mistake. This is the paper that Howard et al referenced in Flexible Paxos as defining the “fundamental theorem of ... Continue Reading

the morning paper

a random walk through Computer Science research, by Adrian Colyer
Made delightfully fast by strattic

Consistency