Distributed consensus and the implications of NVM on database management systems

September 28, 2016November 11, 2019 ~ Adrian Colyer ~ 2 Comments

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

Flexible Paxos: Quorum intersection revisited

September 27, 2016November 11, 2019 ~ Adrian Colyer ~ 6 Comments

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

Distributed Consistency and Session Anomalies

February 26, 2016 ~ Adrian Colyer ~ 13 Comments

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

Generalized Isolation Level Definitions

February 25, 2016 ~ Adrian Colyer ~ 5 Comments

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

A Critique of ANSI SQL Isolation Levels

February 24, 2016 ~ Adrian Colyer ~ 25 Comments

A Critique of ANSI SQL Isolation Levels - Berenson et al. 1995 udpate: 2 minor corrections in the section on A5A per the comment from 'banks' - thanks! The ANSI SQL isolation levels were originally defined in prose, in terms of three specific anomalies that they were designed to prevent. Unsurprisingly, it turns out that ... Continue Reading

Chapar: Certified Causally Consistent Distributed Key-Value Stores

February 8, 2016 ~ Adrian Colyer ~ 1 Comment

Chapar: Certified Causally Consistent Distributed Key-Value Stores - Lesani et al. 2016 Another POPL '16 paper today. The Chapar framework provides for modular verification of causal consistency for both causally consistent key-value store implementations and for client programs written to use them. §1 also wins the prize for best use of emojis in a research ... Continue Reading

‘Cause I’m Strong Enough: Reasoning About Consistency Choices in Distributed Systems

February 3, 2016 ~ Adrian Colyer ~ 3 Comments

'Cause I'm Strong Enough: Reasoning About Consistency Choices in Distributed Systems - Gotsman et al. 2016 With apologies for the longer write-up today, I've tried to stick right to the heart of the matter, but even that takes quite some explanation... We've looked at the theme of coordination avoidance before - instead of uniformly applying ... Continue Reading

PSync: A Partially Synchronous Language for Fault-Tolerant Distributed Algorithms

February 1, 2016 ~ Adrian Colyer ~ 1 Comment

PSync: A Partially Synchronous Language for Fault-Tolerant Distributed Algorithms - Drăgoi et al. 2016 Last month we looked at the RAMCloud team's design pattern for building distributed, concurrent, fault-tolerant modules. Today's paper goes one step beyond a pattern, and introduces a domain-specific language called PSync with the goal of unifying the modeling, programming, and verification ... Continue Reading

Consensus on Transaction Commit

January 13, 2016 ~ Adrian Colyer ~ 4 Comments

Consensus on Transaction Commit - Gray & Lamport 2004/5 Last year on The Morning Paper we spent a considerable amount of time looking at consensus protocols. Over the last couple of days we've been looking at the two-phase commit protocol. But isn't two-phase commit just a special purpose version of the consensus problem, where we ... Continue Reading

Granularity of Locks and Degree of Consistency in a Shared Data Base – Part II

January 6, 2016 ~ Adrian Colyer ~ 3 Comments

Granularity of Locks and Degree of Consistency in a Shared Data Base - Gray et al. 1975 This is part 3 of a 7 part series on (database) 'Techniques Everyone Should Know.' Today we'll look at the second part of this paper which introduces the notion of differing degrees of consistency, and how we can ... Continue Reading

the morning paper

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

Consistency