The last time Hackerfall tried to access this page, it returned a not found error. A cached version of the page is below, or click here to continue anyway

Gryadka is not Paxos, so it's probably wrong (RETRACTED) · Tobias Schottdorf

Gryadka is not Paxos, so it's probably wrong (RETRACTED)

23 Mar 2017

Leslie Lamport purportedly once said (though I cant prove it):

If its not Paxos, its probably wrong.

In the original version of this post, I claimed that gryadka, which claims to be built on top of a Paxos-backed CAS register, was incorrect by providing a counter-example.

It turns out that you really drop 20 IQ points on a vacation, and that I had not at all provided a counter-example, despite having looked closely at the algorithm.

My claim that the Paxos-style CAS register exhibited anomalies is thus wrong (or, at least, unproven).

My apologies to @rystsov, who kindly pointed out my mistake. Ill look into the algorithm more (post-vacation), but now considering that it might be correct, which would be quite exiting - perhaps there are Paxos-like things which are not Paxos but are not wrong.

The original version of this post is available in the commit history, preserved for posterity. My mistake not carrying out the read phase in the middle fully: If you do, then youll commit the old value again, making the anomaly-exhibiting later CAS fail.

Continue reading on tschottdorf.github.io