Putting Consistency Back into Eventual Consistency - Balegas et al. 2015 Today's choice is another pick from the recent crop of Eurosys 2015 papers. Balegas et al. show us that we don't have to put up with weak forms of eventual consistency, even in geo-replicated settings. In Building on Quicksand Helland argued that we need ... Continue Reading

Building on Quicksand - Helland & Campbell 2009 Last week we looked at Consistency analysis in Bloom, and Coordination Avoidance in Database Systems. A common theme in both of these is that some collaboration between the application (understanding of application level semantics) and datastore is key to unlocking the next level of performance. We can ... Continue Reading

Raft Refloated: Do we have consenus? - Howard et al. 2015 This is part ten of a ten-part series on consensus and replication. We're nearing the end of this journey after looking at Viewstamped Replication (and VRR), Paxos, ZooKeeper's atomic broadcast, and Raft. Not that we've exhausted all the literature on these topics - far ... Continue Reading

In Search of an Understandable Consensus Algorithm (Extended Edition) - Ongaro & Ousterhout 2014 This is part 9 of a ten part series on consensus and replication. Here's something to be grateful for: a consensus algorithm with a primary goal of being understandable! The authors also claim it provides a better foundation (than previous algorithms) ... Continue Reading

Vive La Différence: Paxos vs Viewstamped Replication vs Zab - van Renesse et al. 2014 This is part 8 of a ten part series on consensus and replication. Perhaps by now you've started to discern some common patterns in the algorithms we've looked at. A leader or primary; two-phases to each goal the group wants ... Continue Reading

ZooKeeper's Atomic Broadcast Protocol: Theory and practice - Medeiros 2012. This is part 7 in a ten part series on consensus and replication. Perhaps after reading yesterday's paper on Zab you feel like you've got a good high-level understanding of how ZooKeeper atomic broadcast works under the covers. Unfortunately I've got news for you - ... Continue Reading

Zab: High-performance broadcast for primary-backup systems - Junqueira et al. 2011 This is part six of a ten-part series on consensus and replication. This paper describes the atomic broadcast protocol that underpins Zookeeper. Rather than replicate operations as we've seen so far for Paxos and VR, Zab replicates state changes. Critical to the design of ... Continue Reading

Viewstamped Replication Revisited - Liskov & Cowling 2012 This paper presents an updated version of Viewstamped Replication (referred to as VR from now on). VR works in an asynchronous network like the Internet, and handles failures in which nodes fail by crashing. It supports a replicated service that runs on a number of replica nodes. ... Continue Reading