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 Raft Refloated: Do we have consensus?

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 In Search of an Understandable Consensus Algorithm

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 Vive La Différence: Paxos vs Viewstamped Replication vs Zab

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 ZooKeeper’s Atomic Broadcast Protocol: Theory and Practice

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 Zab: High-performance broadcast for primary-backup systems

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 Viewstamped Replication Revisited

Paxos Made Live - An Engineering Perspective - Chandra et. al 2007 This is the fourth paper in a ten-part series on consensus. Yesterday we looked at Paxos Made Simple, today we hear from the the team at Google that implemented Paxos at the core of Chubby. The paper reminds of the following Yogi Berra … Continue reading Paxos Made Live

Paxos made simple - Lamport 2001 This is part 3 of a 10 part series on consenus. Yesterday we looked at The Part-Time Parliament, Lamport's first paper introducing the Paxos algorithm, which takes an allegorical form. In today's choice, Lamport abandons the allegory and puts across the Paxos algorithm in plain english. The Paxos algorithm … Continue reading Paxos made simple