Nice papers. Used “suggest” for these tag changes:
Drop crypto since I see no crypto
Since algorithms and in real-world use, I just suggested programming as generic tag. If not real-world use, could be compsci, programming, or both.
Coincidentally I’ve been working on eventual consistency mechanisms using vector clocks at work lately. The whole subfield is amazing.
The jury is still out as to whether it’s going into the next major version of the product or the next-next major version, but I’d like to see it get in sooner rather than later.
Could you tell us what options you considered, pros/cons you saw, and why you went with vector clocks? People might find that interesting.
Although I dont use any of those mechanisms, I did like the simplicity of the vector clock description. It might be deceptively simple but simple of some sort at least.
Honestly, the biggest problem we’re dealing with currently is whether or not we want immediate consistency or eventual consistency. If we decide on the immediate consistency route then all this research will come to nothing (though it was fun). The eventual consistency route is attractive, but necessarily more complicated.
…I wrote a whole long thing about the problem we’re trying to solve, but then it occurs to me that I probably shouldn’t be talking too much about what I’m doing at work on a public forum, so I’ll just go with the vector clock question:
I chose vector clocks because the number of devices we’re dealing with is practically fixed (changing the number of devices is extremely rare), the number of devices is pretty small (five would be a big number), and I am not a particularly smart man and so I had to pick something I could understand.
Vector clocks aren’t the whole solution, though: they provide a mechanism to get partial ordering, but once you’ve gotten stuff in order, it’s up to you to figure out what to do with them. :)
The problem (in very abstract terms) that I’m trying to solve is that multiple devices can generate “documents” of arbitrary complexity (but with well-defined schemas), and then transmit these documents to a central repository. Two devices could generate “the same” document but the two might not actually be the same because the two devices aren’t required to be configured identically (or because “the same” document was generated at two wildly different times and the configuration on the same device evolved in the interim). Additionally, these documents are built-up piecemeal over time, and transmitted to the central repository at random intervals. Devices are not guaranteed to have synchronized wall clocks.
The vector clock approach gives us an ordering such that for any given element of a document, we can pick the most recent version of an element (we don’t care about older versions and elements are kinda-sorta always unique and thus we only need to worry about the elements in a document and not any conflicts between individual elements). Tombstoning lets us pick when a given element should be deleted.
…that was probably more wall-of-texty than you wanted. Sorry.
Fascinating stuff. Makes sense. Thanks for the explanation.