Update June-28: Thanks to Eyal for finding a bug and suggesting a fix (already incorporated into the post). Let’s consider a simple service that has two main operations: read and write. We expect the service to persist the value passed in write and retrieve it when calling read. Making this service fault tolerant is non-trivial, and encapsulates many … Continue reading A Simple Single-writer
Algorithms
Bizur: A New Key-value Consensus Algorithm
I’d like to discuss a paper we’ve published lately. The paper presents work done at Elastifile.com, building a new kind of consensus algorithm. Before describing what our new system does, let’s see why previous consensus algorithms weren’t sufficient. Most consensus algorithms, like Paxos (which I’ve discussed previously in this blog, here and here), Raft or … Continue reading Bizur: A New Key-value Consensus Algorithm
Understanding Paxos – Part 2
The previous post gave a general overview of the Paxos algorithm. Here's a quick recap: Paxos implements a resilient distributed log, such that items can be added and each item is assigned a unique (and increasing) index. The algorithm can be split into three main blocks: a leader election, a consensus on a single item (also called … Continue reading Understanding Paxos – Part 2
Understanding Paxos – Part 1
The first time I heard of the Paxos algorithm was during my bachelor's degree way back in 2004, when I participated in a Distributed Algorithms course. In the past few years Paxos came up multiple times, usually in the context of a robust implementation of some scalable storage system. It is almost always uttered in … Continue reading Understanding Paxos – Part 1
Distributed Thoughts 