4 ms·

Normally, this is the job of vector clocks in State-based CRDTs Is the author mistaking vector clocks for version vectors? If so he would not be the first; the

Normally, this is the job of vector clocks in State-based CRDTs Is the author mistaking vector clocks for version vectors? If so he would not be the first; the famous Amazon Dynamo white paper makes the same mistake when discussing their CRDT implemenetation. But verson vectors and vector clocks are different things. Alternately, I may be ignorant of a class of CRDTs solved with vector clocks.

macintux 3y ago
At Basho, we also got version vectors and vector clocks reversed, probably thanks to the Dynamo paper. As I recall, it's a subtle difference.
- LAC-Tech 3y ago
  Yeah version vectors were first coined in a very underrated paper from 4 decades ago; "Detection of Mutual Inconsistency in Distributed Systems" [0]. In it they not only invent version vectors, they also perfectly describe what came to be known as the "multi-value register CRDT", some three decades before the term was coined. (Amazon Dyano paper does the same, but only a few years before). Also, it contains this line which always makes me laugh: Network partitioning can completely destroy mutual consistency in the worst case, and this fact has led to a certain amount of restrictiveness, vagueness, and even nervousness in past discussions, of how it may be handled. [0] https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Papers/parker83detection.pdf https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Papers...
- 0x457 3y ago
  IIRC clocks are incremented every time peer sends or receives information, while versions incremented only on mutations.
iamwil 3y ago
I think you're correct. Thanks for the correction. I've updated the post. The difference is subtle, and for those interested, the difference is detailed here: https://haslab.wordpress.com/2011/07/08/version-vectors-are-not-vector-clocks/ https://haslab.wordpress.com/2011/07/08/version-vectors-are-... Vector Clocks need to establish a partial order among a, potentially ever growing, set of events occurring in the processes. Version Vectors need to establish a partial order (more precisely a pre-order) among the replicas in the distributed system.

macintux 3y ago

At Basho, we also got version vectors and vector clocks reversed, probably thanks to the Dynamo paper. As I recall, it's a subtle difference.

LAC-Tech 3y ago
Yeah version vectors were first coined in a very underrated paper from 4 decades ago; "Detection of Mutual Inconsistency in Distributed Systems" [0]. In it they not only invent version vectors, they also perfectly describe what came to be known as the "multi-value register CRDT", some three decades before the term was coined. (Amazon Dyano paper does the same, but only a few years before). Also, it contains this line which always makes me laugh: Network partitioning can completely destroy mutual consistency in the worst case, and this fact has led to a certain amount of restrictiveness, vagueness, and even nervousness in past discussions, of how it may be handled. [0] https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Papers/parker83detection.pdf https://pages.cs.wisc.edu/~remzi/Classes/739/Fall2018/Papers...
0x457 3y ago
IIRC clocks are incremented every time peer sends or receives information, while versions incremented only on mutations.

iamwil 3y ago

I think you're correct. Thanks for the correction. I've updated the post. The difference is subtle, and for those interested, the difference is detailed here: https://haslab.wordpress.com/2011/07/08/version-vectors-are-not-vector-clocks/ https://haslab.wordpress.com/2011/07/08/version-vectors-are-... Vector Clocks need to establish a partial order among a, potentially ever growing, set of events occurring in the processes. Version Vectors need to establish a partial order (more precisely a pre-order) among the replicas in the distributed system.