4 ms·
[1] Eventual convergence is likely the strongest convergence property we can guarantee given unbounded partition durations. I don't think this is true. Consid
by cperciva 15y ago
[1] Eventual convergence is likely the strongest convergence property we can guarantee given unbounded partition durations.
I don't think this is true. Consider the property I call "eventually known consistency", wherein the system can be asked "are all operations performed before time T visible everywhere?", with a "yes"/"maybe" response, where "yes" is guaranteed to eventually be returned after some bounded period of non-partition.
Eventually known consistency can be used to get AP (just ask for the data), CP (let T be the current time; spin until ConsistentUpTo(T) returns true; then perform the read), or CA (in the sense that if as long as a partition does not occur, the algorithm for CP provides a response within a bounded time), and is thus strictly stronger than other properties.
- pbailis 15y agoI'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 agoI think you missed this line. > "yes" is guaranteed to eventually be returned after some bounded period of non-partition
- pbailis 15y agoIf 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 agoAs 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.