Bizur: A New Key-value Consensus Algorithm

I’d like to discuss a paper we’ve published lately. The paper presents work done at, 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

Eventual Consistency

Ever since NoSQL databases came into vogue, we hear more and more about eventual consistency. I want to to try and explain not only the difficulties that eventually consistent databases raise, but also why in some cases they can't be avoided. To simplify the discussion, I'll narrow it down to key-value databases, i.e., databases that support … Continue reading Eventual Consistency