marc_shapiro

Joined 9 years ago

Karma

Submissions

Member since

Dec 10

Recent submissions

These optimisations (whole-string operations, compression, etc.) apply equally to CRDTs. See for instance DOI 10.1145/2957276.2957300. See also the blanket optimisations studied by Carlos Baquero's group (which I doubt could carry over to OT because of the complexity of OT theory).

Comment · 8 years ago

Well, RGA has been proved formally [DOI 10.1145/2933057.2933090]. Regarding Figure 3 of the Treedoc paper, I believe the IDs of dY and dZ are in the correct order, according to the rules in the paper.

Comment · 8 years ago

"Most OT algorithms have been proved incorrect": a better reference is https://doi.org/10.1016/j.tcs.2005.09.066

Comment · 8 years ago

The argument of Sun's paper seems to be that CRDTs have hidden performance costs. Perhaps this is true.

This completely misses the main point. OT is complex, the theory is weak, and most OT algorithms have been proven incorrect (see http://hal.inria.fr/inria-00071213/). AFAIK, the only OT algorithm proved correct is TTF, which is actually a CRDT in disguise.

In contrast, the logic of CRDTs is simple and obvious. We know exactly why CRDTs converge. There are several papers proving that specific CRDTs are indeed correct.

Furthermore, I'm somewhat doubtful of the performance discussion, since Attiya et al. proved that there is a lower bound on the complexity of concurrent editing, independently of the technology used. See http://dx.doi.org/10.1145/2933057.2933090.

Disclaimer: I did not read the paper in detail, just skimmed over it.

Comment · 9 years ago

Some conditional updates are safe; others require to add concurrency control. Our CISE analyser will tell precisely you which side a specific operation falls into. See https://youtu.be/HJjWqNDh-GA and http://dx.doi.org/10.1145/2911151.2911160. Antidote doesn't yet support concurrency control, it's work in progress.

Comment · 9 years ago

If the thing you "put" into is a CRDT, then two concurrent "put" will be merged, if that's OK for your application. If however you want to disallow concurrent "put"s then you need to add some concurrency control to the CRDT layer. See the CISE tool https://youtu.be/HJjWqNDh-GA, http://dx.doi.org/10.1145/2911151.2911160. Antidote doesn't yet support concurrency control, it's work in progress.

Comment · 9 years ago

An efficient implementation of RGA designed for concurrent editing: http://dx.doi.org/10.1145/2957276.2957300

Comment · 9 years ago

A write is fast, because it happens directly at the closest replica, without any inter-replica synchronisation. There is no schema per se; rather the DB is object-oriented, and each application picks the object types it needs from the CRDT library. The library currently covers the basics: registers, flags, sets, maps, lists.

Comment · 9 years ago

This was true of the early CRDT designs, but they have improved since then. You will find plenty of inspiration here: http://dblp.uni-trier.de/pers/hd/b/Baquero:Carlos

Comment · 9 years ago