4
$\begingroup$

In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state to one another "infinitely often". On the receiving end, a replica can merge the received state with its own local state by executing a method m.

In the case of convergent replicated data types, or CvRDTs, the states a replica can take on are elements of a (join-semi)lattice, and the m operation takes the join of the the received state and the local state with respect to the lattice. Also, replicas can update their local state (by calling an update method, u), but only in a way that is inflationary with respect to the lattice (that is, the state can only "get bigger").

My questions have to do with the "infinitely often" bit, and are as follows:

  • Is it just the state transmission that occurs infinitely often, or also the calls to m? That is, does the process running at some replica have to explicitly call the m method in order to do a merge, or are these merges happening infinitely often "in the background"? (It seems to me that it must be happening infinitely often in the background, because otherwise, if a process didn't call m at the end of its run, then its replica wouldn't converge with the others, breaking the eventual consistency guarantee that CvRDTs provide.)

  • But, if merges occur infinitely often, do updates to a CvRDT really have to be inflationary? In the presence of infinitely-often merges, it seems like if a non-inflationary update ever happened, that update would just be lost -- which would be unfortunate, but wouldn't actually pose a problem for convergence. When I look at the proof that CvRDTs are eventually consistent, I don't see the place that the inflationary condition on the u method is required. Why exactly does u have to be inflationary?

  • Finally, the definition of causal history in the paper seems fishy if merges are really happening "infinitely often", because if so there would be "no room" for any other method execution to occur! The k'th method execution would have to be a merge, for all k, wouldn't it? Am I taking "infinitely often" too literally? (Update: Yes, I am taking it too literally! See below.)

Thanks!

(Update: After a Twitter discussion with Niklas Ekström, I understand the meaning of "infinitely often" better. If an event occurs "infinitely often", that doesn't mean anything about the frequency of it occurring; it just means that the event occurs an infinite number of times.

So, if event X occurs infinitely often, and some other event Y occurs once (or some finite number of times), then X is guaranteed to occur after Y, because infinitely many occurrences of X cannot all occur before the occurrence(s) of Y. And here, in particular, there is no way for a replica to update itself and for the neighbors not to find out, because a state transmission will always occur after that update (because there are infinitely many state transmissions, and therefore they can't all occur before that update!).

I'm still not sure if I should be thinking of state transmissions and merges as happening infinitely often, or just state transmissions. But, even if merges also occur infinitely often, my comment above about there being "no room" for any other event to occur doesn't make sense, considering what "infinitely often" actually means.)

$\endgroup$
1
$\begingroup$

From my understanding of CvRDTs (though I haven't read that exact paper recently)

  1. I believe after receiving new state m is always called, however this should be part of the send/receive machinery, rather than something the application has to deal with. That doesn't prevent the application calling m if it sees the need, but in lots of cases there isn't one.

  2. u has to be inflationary otherwise it will get "lost" by a merge. Given a merge could happen at any time, a non-inflationary update could disappear beneath the CvRDT user as they were performing operations on it. And while non-inflationary updates don't pose a problem for convergence, they do pose a problem for equality: a <merge> b may not be deterministic in the presence of non-inflationary updates.

  3. I don't have an answer for this. Maybe it's worth reading as "unboundedly many times between each update", but that's a guess.

$\endgroup$
  • $\begingroup$ Can you give an example of what you mean by "a <merge> b may not be deterministic in the presence of non-inflationary updates"? $\endgroup$ – Lindsey Kuper Apr 17 '14 at 21:50
  • $\begingroup$ No, I can't, which suggests I'm wrong. One example of a CvRDT that converges, but not all writes are inflationary is the lattice of integers with 'max'. Two servers could concurrently perform the inflationary write "+1", and after merge, both updates are not preserved, only one is. But that's also slightly to do with people thinking MaxInt could be a counter when for the non-inflationary-updates reason, it really cannot. $\endgroup$ – Sam Elliott Apr 18 '14 at 16:51
  • $\begingroup$ But with MaxInt, those aren't non-inflationary updates. (Non-inflationary means that the state moves downward in the lattice.) And, yeah, whether the updates are preserved depends on whether increments at different replicas are considered the same update or different updates. But that's neither here nor there. $\endgroup$ – Lindsey Kuper Apr 20 '14 at 15:59
0
$\begingroup$

from section 2.1:

Systems that deliver every update to every replica eventually in a fault tolerant manner are well-known in the literature, for instance gossip or anti-entropy approaches [5,13]. For simplicity, we will assume hereafter a fully connected communication graph, where every arc is a fair-lossy channel. Infinitely often, the replica at pi sends (if it is correct) its current state to pj ; replica pj (if it is correct) merges the received state into its local state by executing method m.

"Infinitely Often" is a simplification. The requirement is, like all eventually consistent systems, that all updates eventually reach all replicas (which as the paper eludes, is well-known)

$\endgroup$
  • $\begingroup$ Yep, that's the part of the paper I'm quoting when I say "infinitely often". The proof of SEC for CvRDT objects already assumes eventual delivery (that is, that all updates eventually reach all replicas), and it also assumes termination, so the only thing it has to show is strong convergence. So, where is the "state transmission occurs infinitely often" assumption actually used? And what's the scope of "infinitely often" in that sentence -- does it apply to both the state transmission and to the merge, or just to the state transmission? $\endgroup$ – Lindsey Kuper Apr 17 '14 at 22:07
  • $\begingroup$ I'm probably missing something formal here but I see the "infinitely often" comment as ancillary, except for the fact that its a simple way of guaranteeing the eventual delivery assumption. $\endgroup$ – Jordan West Apr 18 '14 at 15:26
0
$\begingroup$

The proof of SEC for CvRDT objects already assumes eventual delivery (that is, that all updates eventually reach all replicas), and it also assumes termination, so the only thing it has to show is strong convergence. So, where is the "state transmission occurs infinitely often" assumption actually used?

The assumption that "state transmission occurs infinitely often" is necessary for the "eventual delivery" assumption, which in turn is required by the proof of SEC for CvRDT objects.

Specifically, the paper assumes a fair lossy channel system, where messages can be lost while they are in transit but with an additional fairness assumption that the channel delivers infinitely many messages if infinitely many messages are transmitted to it. This fairness assumption about the lossy channel, along with the "state transmission occurs infinitely often" made in this paper, guarantees eventual delivery (of every update).

And what's the scope of "infinitely often" in that sentence -- does it apply to both the state transmission and to the merge, or just to the state transmission?

It applies to both.

As explained before, each correct replica sends its current state to other replicas infinitely often to guarantee the eventual delivery of every update made at this replica.

In principle, each time a replica receives a state message, it calls the merge function to merge the state message into its current state. However, in implementation, this can be optimized to call the merge function only once for each different state message, for example, by distinguishing the state messages by replica ids and local sequence numbers.

For simplicity, we will assume hereafter a fully connected communication graph, where every arc is a fair-lossy channel. Infinitely often, the replica at $p_i$ sends (if it is correct) its current state to $p_j$; replica $p_j$ (if it is correct) merges the received state into its local state by executing method $m$.

Note that it is not necessary for $p_i$ to send each of its states infinitely often. It is sufficient for a replica to send its current state infinite often. This suffices to guarantee the eventual delivery of every update (not every state) made at this replica to other replicas, since all the updates have been integrated into the current state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.