Paxos Made Live

March 5, 2015 ~ Adrian Colyer ~ 6 Comments

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 simple

March 4, 2015 ~ Adrian Colyer ~ 11 Comments

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

The Part-Time Parliament

March 3, 2015 ~ Adrian Colyer ~ 4 Comments

The Part-Time Parliament - Lamport '90/'98 This is part 2 of a 10-part series on consensus. There's quite the back story to this paper. First submitted in 1990, researchers at the time didn't seem to take it seriously due to its presentation as an allegory, and failed to appreciate the fundamental contribution that we know ... Continue Reading

Viewstamped replication: A new primary copy method to support highly available distributed systems

March 2, 2015 ~ Adrian Colyer ~ 4 Comments

Viewstamped replication: A new primary copy method to support highly available distributed systems - Oki & Liskov '88. Given a set of co-operating nodes that form a group, how can we replicate information to group members and maintain a consistent "one copy serializability" property as group members come and go? Oki and Liskov introduce two ... Continue Reading

Can’t we all just agree?

March 1, 2015 ~ Adrian Colyer ~ 29 Comments

(Post updated to add links to write-ups of the papers now that the series is complete). We had to get here at some point! Inspired by the recent publication of Raft Refloated I thought it would be a good time to do a mini-series on consensus. Initially I'd planned out a series of 5 papers ... Continue Reading

The Chubby lock service for loosely coupled distributed systems

February 13, 2015 ~ Adrian Colyer ~ 4 Comments

The Chubby lock service for loosely coupled distributed systems - Burrows '06 This paper describes the Chubby lock service at Google, which was designed as a coarse-grained locking service, found use mostly as a name service and configuration repository, and inspired the creation of Zookeeper. [Chubby's] design is based on well-known ideas that have meshed ... Continue Reading

ZooKeeper: wait-free coordination for internet scale systems

January 27, 2015 ~ Adrian Colyer ~ 4 Comments

ZooKeeper: wait-free coordination for internet scale systems - Hunt et al. (Yahoo!) 2010 Distributed systems would be much simpler if the distributed parts didn't have to coordinate in some fashion. But it's this notion of 'working together' to achieve some aim that differentiates a distributed system from an unrelated bag of parts. Examples of the ... Continue Reading

SwiftCloud: Fault-tolerant geo-replication integrated all the way to the client

November 27, 2014 ~ Adrian Colyer ~ 5 Comments

SwiftCloud: Fault-tolerant geo-replication integrated all the way to the client machine - Zawirski et al. 2013 Data is stored in the cloud, presentation is on mobile devices, and application processing is increasingly split between the two. As mobile devices get more and more capable, we would like to exploit more and more of that capability. ... Continue Reading

The Declarative Imperative: Experiences and Conjectures in Distributed Logic

November 13, 2014 ~ Adrian Colyer ~ 13 Comments

The Declarative Imperative: Experiences and Conjectures in Distributed Logic - Hellerstein 2010. This paper is an extended version of an invited talk that Joe Hellerstein gave to the ACM PODS conference in 2010. The primary audience is therefore database researchers, but there's some good food for thought for the rest of us in there too. ... Continue Reading

An Evaluation of Amazon S3’s Consistency Behavior

November 12, 2014 ~ Adrian Colyer ~ 2 Comments

Eventual Consistency: How soon is eventual? An Evaluation of Amazon S3's Consistency Behavior - Bermbach and Tai, 2011 In honour of AWS re:Invent this week, and since we've already covered the excellent Dynamo paper at #31 in this series, here's a paper looking at eventual consistency and the behaviour of S3. In this work we ... Continue Reading

the morning paper

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

Consistency