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 Millions of tiny databases
Tag: Consistency
Consistency in datastores and distributed systems
Seeing is believing: a client-centric specification of database isolation
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 Seeing is believing: a client-centric specification of database isolation
ACIDRain: concurrency-related attacks on database backed web applications
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 ACIDRain: concurrency-related attacks on database backed web applications
Hybrids on Steroids: SGX-based high-performance BFT
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 Hybrids on Steroids: SGX-based high-performance BFT
Incremental consistency guarantees for replicated objects
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 Incremental consistency guarantees for replicated objects
The many faces of consistency
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 The many faces of consistency
Just say NO to Paxos overhead: replacing consensus with network ordering
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 Just say NO to Paxos overhead: replacing consensus with network ordering
The SNOW theorem and latency-optimal read-only transactions
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 SNOW theorem and latency-optimal read-only transactions
The Honey Badger of BFT protocols
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 Honey Badger of BFT protocols
The load, capacity, and availability of quorum systems
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 load, capacity, and availability of quorum systems
the morning paper 