Granularity of Locks and Degree of Consistency in a Shared Data Base - Gray et al. 1975 This is part 2 of a 7 part series on (database) 'Techniques Everyone Should Know.' This is a paper of two halves, connected by the common theme of locking. The first part of the paper examines the tradeoff … Continue reading Granularity of Locks and Degree of Consistency in a Shared Data Base – Part I
Tag: Consistency
Consistency in datastores and distributed systems
Implementing Linearizability at Large Scale and Low Latency
Implementing Linearizability at Large Scale and Low Latency - Lee at al. 2015 Yesterday we saw how to layer a strictly serializable transaction model on top of an inconsistent replication protocol. Previously we've also looked at how to bolt-on a causal consistency model on top of eventual consistency. Today's paper demonstrates how to bolt-on (layer) … Continue reading Implementing Linearizability at Large Scale and Low Latency
Existential Consistency: Measuring and Understanding Consistency at Facebook
Existential Consistency: Measuring and Understanding Consistency at Facebook - Lu et al. 2015 At the core of this paper is an analysis of the number of anomalies seen in Facebook's production system for clients of TAO, which is impressively low under normal operation (0.0004%) - to interpret that number of course, we'll have to dig … Continue reading Existential Consistency: Measuring and Understanding Consistency at Facebook
Consistency Without Borders
Consistency Without Borders - Alvaro et al. 2013 We closed out last week by looking at the gap that has opened up between application developer needs and what the database community is providing, leading to the widespread adoption of Feral Concurrency Control. Today's paper, written two years earlier, anticipates this problem and discusses the possible … Continue reading Consistency Without Borders
The Potential Dangers of Causal Consistency and an Explicit Solution
The Potential Dangers of Causal Consistency and an Explicit Solution - Bailis et al. 2012 Yesterday we saw how we could get both better performance and stronger consistency by upgrading from eventual consistency to causal consistency. Are there any downsides? With useful semantics, low latency, partition tolerance, and, recently, a demonstrably efficient architecture, causal consistency … Continue reading The Potential Dangers of Causal Consistency and an Explicit Solution
Bolt-on Causal Consistency
Bolt-on Causal Consistency - Bailis et al. 2013 "It'll probably be OK" seems to reflect the prevailing application developer's attitude to working with eventually consistent stores. Thanks to the work of Bailis et al. on PBS, we can now quantify that 'probably.' And it looks pretty good at first glance, with 99+% probabilities achievable after … Continue reading Bolt-on Causal Consistency
Probabilistically Bounded Staleness for Practical Partial Quorums
Probabilistically Bounded Staleness for Practical Partial Quorums - Bailis et al. 2012, and Quantifying Eventual Consistency with PBS - Bailis et al. 2014 'Probabilistically Bounded Staleness... ' was the original VLDB '12 paper, and then the authors were invited to submit an extended version to the VLDB Journal ('Quantifying Eventual Consistency...') which was published in … Continue reading Probabilistically Bounded Staleness for Practical Partial Quorums
Lasp: A language for distributed, coordination-free programming
Lasp: A language for distributed, coordination-free programming - Meiklejohn & Van Roy 2015 * Update: fixed typo in Chris' surname above. * With thanks to Colin Barrett for suggesting today's choice, and to Chris Meiklejohn for providing a link to a paywall-free preprint of the paper. Christopher Meiklejohn recently announced he is leaving Basho to … Continue reading Lasp: A language for distributed, coordination-free programming
Global Sequence Protocol
Global Sequence Protocol: A Robust Abstraction for Replicated Shared State - Burckhardt et al. 2015 This is the ECOOP '15 paper that we've been building up to so far this week. The problem domain is the familiar desire to support replicated shared data across nodes (mobile devices here) with eventual consistency. In the mobile context, … Continue reading Global Sequence Protocol
Practical Byzantine Fault Tolerance
Practical Byzantine Fault Tolerance - Castro & Liskov 1999 Oh Byzantine, you conflict me. On the one hand, we know that the old model of a security perimeter around an undefended centre is hopelessly broken (witness Google moves its Corporate Applications to the Internet)- so Byzantine models, which allow for any deviation from expected behaviour … Continue reading Practical Byzantine Fault Tolerance
the morning paper 