Unanimous: System Research Group talklet

Screen Shot 2015-04-14 at 08.44.05

I’m looking forward to sharing my thoughts on consensus for the edge network with the SRG today, abstract below

Many projects in the SRG at the moment (HAT, UCN, contacts app, MirageOS for ARM, Jitsu, databox, signposts) are trying to give individuals an viable alternative to 3rd party centralised services and put them back in control of their personal data. However developing applications for the hostile edge network, with its heterogeneous hosts and networks, trust issues and poorly understood middle boxes is tricky. This is made worse by the fact that consensus algorithms are famously difficult to use, underspecified and based on decade old assumption about the internet. In this talklet, I will motivate Unanimous, a new consensus algorithm for the modern internet.

NB: this is a practice talk for EuroSys doctoral workshop next Tuesday, thus this 5 min talk will simply motivate a research direction instead of presenting a complete solution.
EDIT (17/4): these slides are now online

Raft Refloated: Do We Have Consensus?

The January edition of SIGOPS Operating Systems Review is out now and thus is the aptly named “Raft Refloated: Do We Have Consensus?”. This is my first journal paper and I’m really existed to see what the community makes of it.

Title: Raft Refloated: Do We Have Consensus?
Authors: Heidi Howard, Malte Schwarzkopf, Anil Madhavapeddy and Jon Crowcroft
Paper: acm dl, open access link
Abstract: The Paxos algorithm is famously difficult to reason about and even more so to implement, despite having been synonymous with distributed consensus for over a decade. The recently proposed Raft protocol lays claim to being a new, understandable consensus algorithm, improving on Paxos without making compromises in performance or correctness.

In this study, we repeat the Raft authors’ performance analysis. We developed a clean-slate implementation of the Raft protocol and built an event-driven simulation framework for prototyping it on experimental topologies. We propose several optimizations to the Raft protocol and demonstrate their effectiveness under contention. Finally, we empirically validate the correctness of the Raft protocol invariants and evaluate Raft’s understandability claims.

Below is the key figure of the paper, showing a side-by-side comparison of the simulation results next to the authors’ original results.

fig15-original

fig15-replicate

Release of “ARC: Analysis of Raft Consensus”

 “ARC: Analysis of Raft Consensus” is now available online as a UCAM technical report. 
http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-857.pdf

Abstract

The Paxos algorithm, despite being synonymous with distributed consensus for a decade, is famously difficult to reason about and implement due to its non-intuitive approach and underspecification. In response, this project implemented and evaluated a framework for constructing fault-tolerant applications, utilising the recently proposed Raft algorithm for distributed consensus. Constructing a simulation framework for our implementation enabled us to evaluate the protocol on everything from understandability and efficiency to correctness and performance in diverse network environments. We propose a range of optimisations to the protocol and released to the community a testbed for developing further optimisations and investigating optimal protocol parameters for real-world deployments.

Thank you everyone for your feedback.

Seeking Feedback on “ARC: Analysis of Raft Consensus”

My undergraduate dissertation “ARC: Analysis of Raft Consensus” will be submitted as a UCAM tech report. A draft is available here and I would be very grateful of any feedback.

Title: ARC: Analysis of Raft Consensus

Abstract:
The Paxos algorithm, despite being synonymous with distributed consensus for a decade, is famously difficult to reason about and implement due to its non-intuitive approach and underspecification. In response, this project implemented and evaluated a framework for constructing fault-tolerant applications, utilising the recently proposed Raft algorithm for distributed consensus. Constructing a simulation framework for our implementation enabled us to evaluate the protocol on everything from understandability and efficiency to correctness and performance in diverse network environments. We propose a range of optimisations to the protocol and released to the community a testbed for developing further optimisations and investigating optimal protocol parameters for real-world deployments.

EDIT 1: Regarding the difference between this tech report and my dissertation. I have cut out material i didn’t believe would be of general interest, such as how i used VC or lessons learned. If you would like a copy of the original dissertation (probably because your a Part 2 student yourself), just email me and I’ll be happy to provide you a copy.

EDIT 2: I’m pretty much happy to take feedback by any format, Comment below or email me at hh360 @ cam . ac . uk

EDIT 3: A massive thankyou to everyone who has provided feedback and help to disseminate this draft (by retweeting it)

EDIT 4: The code is open source (MIT licence) and available on GitHub. I’ve not linked to as its currently undergoing a refactoring / documenting process ready for release of v0.1. My plan is split the code base into two separate libraries, one will be a event-based simulator for distributed system and the other will be a standalone Raft implementation. I’ll update this blog (& twitter) when the code is ready

EDIT 5:  Wow. The response to this draft has been much greater than I expected (300+ downloads so far). Thank you so much to everyone in the community and of course Diego Ongaro. Diego’s Raft paper is online here and the Raft consensus site is here.