Hacker News Reader

> Secondly, Antirez's argument that you can use a compare & swap in a transactional storage layer is also wrong. This is not possible to write safely.

Could you elaborate on this? I'm not sure I'm as pessimistic as you on this one point.

View on HN

Compare and swap has a consensus number of 2. A consensus number is the maximum number of processes for which the object can solve a simple consensus problem. It is impossible to construct a wait-free implementation of an object with consensus number n from an object with a lower consensus number. In other words, test-and-set is weaker than transactions or Paxos for >2 concurrent clients.

http://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf

Wait, compare and swap has a consensus number of infinite (from Herlihy's paper).

Oops, you're right. I was thinking of test-and-set.

In short, either the storage layer provides enough guarantees to ensure safety without redlock OR it is not possible to ensure safety.

I believe that antirez's proposal is the former, but if he has a safe algorithm that does not require a linearizable CAS operation in the storage layer and is safe w/ redlock, I would love to hear it.

I also provided an example of how to use Cassandra which is eventually consistent safely with a locking service that provides monotonic tokens.

Reply on news.ycombinator.com