vorset2:merge/2 is not commutative and other bugs

[lenary]

So we at basho have been looking at your work (yay, CRDTs). We have a quickcheck suite for testing CRDTs, which we've been having success with (it's here, if you're interested: https://github.com/basho/riak_dt/blob/multi_crdt/test/crdt_statem_eqc.erl ).

Firstly, there are obvious bugs in your program. You treat the pairs in the values section at times as {Element, ID}, and at other times as {ID, Element}.

Secondly, your merge function does not commute. We wrapped your implementation in the same interface as we had, and it was failing our tests for equality, which have to be based on the fact that merge/2 commutes.

I rewrote the module into one with a deterministic, commutative merge function, but I'm not sure if it's the same algorithm as specified in the accompanying paper, so it may not be "optimised". My function also relies on the ordering of timestamps, which may be problematic.

My alterations to the module are here: https://gist.github.com/lenary/5755145 (I did quite a bit of a rewrite, to use ord{dict,sets} everywhere, to remove bugs, and to make merge/2 commute.

[Licenser]

Hi @lenary,
thanks a lot for the input :) you're totally right with the {Element, ID} option thanks for catching this :)!

And you're right the merge function had a bug, fixed it, thanks mate!

So your alterations are somewhat faulty (in the sense of the CRTD) it does loose remove statements on the merge see the following example:

when all are connected add an element, disconnect, remove the element from partition A, rejoin and merge -> the element reappears in A but should disappear in B.

Cheers,
Heinz