https://haslab.wordpress.com/2011/07/08/version-vectors-are-not-vector-clocks/ HASlab High Assurance Software Laboratory Skip to content * Home * About [water-drops] - Convergent and Commutative Replicated Data Types Conflict-free Replicated Data Types - Version Vectors are not Vector Clocks Posted on July 8, 2011 by Carlos Baquero | 5 Comments Most people still confuse Version Vectors and Vector Clocks. Well, I did confuse them for several years. In fact they look the same and the update rules are almost the same. Both of these mechanisms are practical ways of capturing causality in distributed systems. Causality (in distributed systems) is an abstract concept, can was formalized in 1978 by Leslie Lamport in one of the most cited articles in computer science. In 1983 Version Vectors are developed to track the causal relations among data items that can be concurrently updated. Some years later, around 1988, Vector Clocks are developed to track the causality between events in a distributed computation. In both cases a vector of integers, one per source of concurrency, is used. There is, however, a fundamental difference. First, in order to simplify a little bit, lets consider that we have a fixed number of processes and a fixed number of replicas. * Vector Clocks need to establish a partial order among a, potentially ever growing, set of events occurring in the processes. The set of events that are generated in the distributed computation. Naturally since the set can grow unbounded, the tracking mechanism also needs to grow unbounded. Vectors of integers are fine since, at least in theory we don't run out of integers. In 1991, Charron-Bost showed in this article that Vector Clocks are the smaller mechanism that can track causality among distributed events. * Version Vectors need to establish a partial order (more precisely a pre-order) among the replicas in the distributed system. Notice that although the state in these replicas changes as consequence of ever growing sets of update events, here we want to relate the replica states and not the update events. Using vectors of integers is over-expressive in this setting. In 2004, we noticed this and constructed Bounded Version Vectors, where integers are substituted by a limited set of symbols, depending on the number of replicas. Naturally, Charron-Bost result does not apply to Version Vectors. Lets consider a simple example, thats shows that vectors of integers are over-expressive . One has two recently synchronized replicas A and B with identical state and vectors A[2,3] and B[2,3]. Now, replica A suffers an update and its new vector is A[3,3]. We now see that A is more updated than B, since [3,3] > [2,3] (here each integer in the left is greater or equal than its counterpart in the same position). Now replica A suffers 7 more updates, A[10,3]. Still we have [10,3] > [2,3], and this increase in the integer does not convey more information to the task of tracking the causal order among the two replicas. The number of individual updates is typically not important, specially in systems where you can change either a lot or a little in a single update. What is important is how they change the causal order relation among the replicas. In the example, at this point, we can compare A[10,3] and B[2,3] and notice that they are easy to synchronize since A has the most updated state and it can be simply copied into B. However, if B issues an update and we now have a system with A[10,3] and B[2,4]. Now the replicas are divergent and a synchronization will typically have to look at the state (often with user assistance) to figure the correct synchronized state that can be tagged with [10,4]. The message is, use the right tools and know the differences. Vector Clocks are great to implement causal delivery middleware, consistent snapshots, and the like. But for replicated data, Version Vectors are the right concept, and several mechanisms can make use of the subtle differences. Our own work on Dotted Version Vectors explores this and a specific system interaction that occurs in present data-stores. We also point out to Concise Version Vectors that explores the synchronization of multiple replicas and early work on dynamic version vector maintenance. Share this: * Twitter * Facebook * More * * Reddit * Like this: Like Loading... Related This entry was posted in Distributed Systems. Bookmark the permalink. - Convergent and Commutative Replicated Data Types Conflict-free Replicated Data Types - 5 responses to "Version Vectors are not Vector Clocks" 1. [c3bfa] hengxin1102 | June 13, 2014 at 2:36 am | Reply I have always thought that vector clock and version clock were the same thing before reading this article. It is the theorem of Charron-Bost that reminds me that they are actually different: otherwise your dotted version clock cannot be right. I am wondering whether there is some theorem on version clock, analogous to the Charron-Bost theorem on vector clock. 2. [c3bfa] hengxin1102 | June 13, 2014 at 2:41 am | Reply Reblogged this on distributed2thought. 3. [c3bfa] hengxin1102 | June 13, 2014 at 3:25 am | Reply In the "simple example", you have commented that "The number of individual updates is typically not important, specially in systems where you can change either a lot or a little in a single update." Does the "individual updates" mean the updates made by a single process? What do you mean by "you can change either a lot or a little in a single update"? Could you give some examples? 4. [6fc26] Carlos Baquero | June 13, 2014 at 9:33 am | Reply Hi, on the "change either a lot or a little in a single update" means to say that small changes or big changes to a replica can both be detected by advancing a clock entry by 1. The magnitude of the change is not important, so if you change a word or a whole paragraph, its the same. Its a bit like doing copy-on-write on memory pages, it doesn't mater how much you changed. 5. [c3bfa] hengxin1102 | August 6, 2014 at 2:36 am | Reply Is my understanding right: For a distributed storage system, what the dotted version clock is tracking is the causality among *replica states* instead of among the *update events* modifying the states. In vector clock with one entry per client, the causal history is a set of *events*. However, in dotted version clock, the causal history is now a set of *replica states*, from which we cannot restore the origin *update events* which bring the initial state to the current one. I have read your paper "Dotted Version Vectors: Logical Clocks for Optimistic Replication" which takes the typical key-value store as example. In particular, dotted version vector is used for eventual consistency. My questions are (1) Can DVV be used for causal consistency? (2) How to capture causality among replica states over different keys? (3) Is DVV suitable for the conversation scenario in social network in which people can reply to a post and also to another reply. The replies are causally organized in the natural way. I am still quite confused about (dotted) version clock. May I have your comments on these questions? Great thanks. Leave a Reply Cancel reply Enter your comment here... [ ] Fill in your details below or click an icon to log in: * * * * * Gravatar Email (required) (Address never made public) [ ] Name (required) [ ] Website [ ] WordPress.com Logo You are commenting using your WordPress.com account. ( Log Out / Change ) Google photo You are commenting using your Google account. ( Log Out / Change ) Twitter picture You are commenting using your Twitter account. ( Log Out / Change ) Facebook photo You are commenting using your Facebook account. ( Log Out / Change ) Cancel Connecting to %s [ ] Notify me of new comments via email. [ ] Notify me of new posts via email. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] * Authors + [a12f9] Alcino Cunha + [6fc26] Carlos Baquero + [4bdeb] Jose C. Campos + [fee2a] Jorge Sousa Pinto + [a34f3] Paulo Silva Blog at WordPress.com. [Close and accept] Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy * Follow Following + [wpcom-] HASlab Join 1,990 other followers [ ] Sign me up + Already have a WordPress.com account? Log in now. * + [wpcom-] HASlab + Customize + Follow Following + Sign up + Log in + Copy shortlink + Report this content + View post in Reader + Manage subscriptions + Collapse this bar %d bloggers like this: [b]