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

Distributed consensus and the implications of NVM on database management systems

Distributed consensus and the implications of NVM on database management systems Fournier, Arulraj, & Pavlo ACM Queue Vol 14, issue 3 As you may recall, Peter Bailis and ACM Queue have started a "Research for Practice" series introducing "expert curated guides to the best of CS research." Aka, reading lists for The Morning Paper! I … Continue reading Distributed consensus and the implications of NVM on database management systems

Flexible Paxos: Quorum intersection revisited

Flexible Paxos: Quorum intersection revisited Howard et al., 2016 Paxos has been around for 18 (26) years now, and extensively studied. (For some background, see the 2 week mini-series on consensus that I put together last year). In this paper, Howard et al. make a simple(?) observation that has significant consequences for improving the fault-tolerance … Continue reading Flexible Paxos: Quorum intersection revisited

Distributed Consistency and Session Anomalies

Since we've spent the last couple of days sketching anomaly diagrams and looking at isolation levels, I wanted to finish the week off with a quick recap of session anomalies and consistency levels for distributed stores. In terms of papers, I've drawn primary material for this from: Highly Available Transactions: Virtues and Limitations, and Linearizability … Continue reading Distributed Consistency and Session Anomalies

Generalized Isolation Level Definitions

Generalized Isolation Level Definitions - Adya et al. 2000 Following on from yesterday's critique of ANSI SQL isolation levels, today's paper also gives a precise definition of isolation levels - but does so in a way that is inclusive of optimistic and general multi-version concurrency control strategies instead of being dependent on locking. Where Berenson … Continue reading Generalized Isolation Level Definitions