slash dev slash null

simbo1905’s ramblings about computers

Tag: distributed

One More Frown Please? (UPaxos Quorum Overlaps)

There was some discussion around UPaxos safety on a gist where Dave Turner was kind enough to clarify a confusion of mine. I had said that we needed an overlap between prepare quorums to avoid a split-brain. This was incorrect and I am greatful for Dave for correcting my misunderstanding. Yet there was something about not having that overlap that was bugging me… This morning I had an “Aha!” moment: if it exists then Trex will perform an optimisation. Yet in Trex this overlap is not enforced.

Read the rest of this entry »

UPaxos: Unbounded Paxos Reconfigurations

The year 2016 turned out to be a bumper year for pragmatic Paxos discoveries. Hot on the heels of the FPaxos discovery of more flexible quorums comes Unbounded Pipelining in Dynamically Reconfigurable Paxos Clusters or “UPaxos”. This uses overlapping quorums between consecutive cluster configurations, and a leader “casting vote”, to enable cluster reconfigurations in a non-stop manner even when reconfiguration messages are lost. Read the rest of this entry »

Paxos Reconfiguration Stalls

In a previous post I covered using the Paxos engine itself to do cluster reconfiguration as per the 2001 Paxos Made Simple paper. In this post I will cover a problem with that technique know as pipeline stalls. This post is to set the scene for a new technical report published 2016 which fixes the problem with a state-of-the-art Paxos implementation called UPaxos which we will discuss in the next post. Read the rest of this entry »

Cluster Replication With Paxos

In my last post I made the case for the defence of the Paxos Algorithm. In this post we will delve into a tough problem which Paxos solves; state replication across a cluster of replicas using atomic broadcast. It turns out that maintaining primary ordering on secondary servers is straightforward to achieve using Paxo without affecting correctness or efficiency. This may be a surprising result to any reader who has looked at ZAB and Raft. You don’t need an external leader election service as used in the Spinnaker or PaxStore papers. You send the highest committed, and highest proposed, log stream sequence counter during leader failover, and introduce optional, ignorable, retransmission requests. The techniques described in this article are used by the Trex Paxos library.

Read the rest of this entry »