News for hackers. Stuff that matters.
Re:Is Redlock Safe? Reply to Redlock Analysis by jhugg on Tuesday February 09, 2016 @12:04PM (#11066766)
> 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.

Re:Is Redlock Safe? Reply to Redlock Analysis by jamesblonde on Tuesday February 09, 2016 @03:00PM (#11068301)
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

Re:Is Redlock Safe? Reply to Redlock Analysis by jhallenworld on Tuesday February 09, 2016 @05:14PM (#11069229)
Wait, compare and swap has a consensus number of infinite (from Herlihy's paper).
Re:Is Redlock Safe? Reply to Redlock Analysis by jamesblonde on Wednesday February 10, 2016 @02:25AM (#11071234)
Oops, you're right. I was thinking of test-and-set.
Re:Is Redlock Safe? Reply to Redlock Analysis by carllerche on Tuesday February 09, 2016 @12:46PM (#11067117)
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.