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.)
(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.)