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.
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.
Could you elaborate on this? I'm not sure I'm as pessimistic as you on this one point.