3 ms·

I'm not sure I entirely follow your argument. I agree that you can use some sort of heartbeat protocol or negative acknowledgments to determine whether writes o

by pbailis 15y ago

I'm not sure I entirely follow your argument. I agree that you can use some sort of heartbeat protocol or negative acknowledgments to determine whether writes occurred within a given time window (e.g., I haven't heard from the cluster, so maybe I missed an update in the time since the last heartbeat). However, in general, I don't believe it's possible to guarantee non-trivial convergence for fixed T and unlimited partition durations. For any given T, if I partition each of your nodes for T+1 seconds, you won't be able to guarantee convergence--your nodes won't communicate. Am I missing something?

Dylan16807 15y ago
I think you missed this line. > "yes" is guaranteed to eventually be returned after some bounded period of non-partition
- pbailis 15y ago
  If you can bound partition durations, you can definitely make stronger guarantees. If you can model your network delays, you can use some modeling like our work on PBS (Probabilistically Bounded Staleness) to predict staleness: http://pbs.cs.berkeley.edu/#demo http://pbs.cs.berkeley.edu/#demo
cperciva 15y ago
As Dylan16807 said, the key property in "eventually known consistency" is that when partitions don't happen you'll eventually get a "yes, that write has propagated everywhere" answer. You can do this with gossiping updates and two clock vectors (vector #1 is "I have seen all the writes node X did up to this time", and vector #2 is "node X says it has seen everything done by any node prior to this time"). While you have partitions, you'll get a "maybe" back, because you can't distinguish between the cases of "a write hasn't propagated everywhere" and "it has propagated everywhere but I haven't received an ACK for it"; that's unavoidable, but doesn't mean that this is not useful anyway.

3 ms·

I'm not sure I entirely follow your argument. I agree that you can use some sort of heartbeat protocol or negative acknowledgments to determine whether writes o

by pbailis 15y ago

Dylan16807 15y ago
I think you missed this line. > "yes" is guaranteed to eventually be returned after some bounded period of non-partition
- pbailis 15y ago
  If you can bound partition durations, you can definitely make stronger guarantees. If you can model your network delays, you can use some modeling like our work on PBS (Probabilistically Bounded Staleness) to predict staleness: http://pbs.cs.berkeley.edu/#demo http://pbs.cs.berkeley.edu/#demo
cperciva 15y ago
As Dylan16807 said, the key property in "eventually known consistency" is that when partitions don't happen you'll eventually get a "yes, that write has propagated everywhere" answer. You can do this with gossiping updates and two clock vectors (vector #1 is "I have seen all the writes node X did up to this time", and vector #2 is "node X says it has seen everything done by any node prior to this time"). While you have partitions, you'll get a "maybe" back, because you can't distinguish between the cases of "a write hasn't propagated everywhere" and "it has propagated everywhere but I haven't received an ACK for it"; that's unavoidable, but doesn't mean that this is not useful anyway.