Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Real Differences Between OT and CRDT for Co-Editors

arxiv.org

Post reply on HN
Print view View original

61–66 of 66 posts

Re: Real Differences Between OT and CRDT for Co-Editors

#61

Post by nused »

marc_shapiro wrote: post #57
marc_shapiro wrote: post #56

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…

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

This paper follows the same reasoning as in http://hal.inria.fr/inria-00071213/, so it invariably arrives at the same bogus conclusion "Most OT algorithms have been proved incorrect". Please feel free to explain if you feel otherwise, but quoting yet another publication doesn't really help its case here.

What did catch my eye in this paper is that the authors claimed to have used CoWord as a case study (and of course, claimed that the theorem prover showed CoWord doesn't satisfy TP2). I worked on CoWord, and it was never open-sourced so how the authors got hands on CoWord's transformation functions (which were inside a compiled C++ binary OT-engine) for evaluation is truly troubling. Care to explain?

Re: Real Differences Between OT and CRDT for Co-Editors

#62

Post by marc_shapiro »

nused wrote: post #43
amsha wrote: post #14

Here's the key sentence: "concrete implementations of CRDT in co-editors revealed key missing steps in CRDT literature." This paper may be correct for academic CRDTs but it is very wrong when looking at industry implementations. My hunch is that because CRDTs are so much easier to grok than OT, engineers are empowered to make use case-specific improvements that aren't reflected in academic literature. For example, th…

Casual and blanket theoretical characterizations of OT and CRDT algorithms is exactly the kind of folly that the article is trying to address. For example, it's a logical contradiction to begin the statement with "OT's complexity is _generally_ governed by editing history (H), i.e. O(H)" to conclude that "CRDTs have much better perf than OT", then adding a qualification that argument applies only for the specific off…

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

Re: Real Differences Between OT and CRDT for Co-Editors

#63

Post by nused »

marc_shapiro wrote: post #62
nused wrote: post #43

Earlier quoted context omitted.

Casual and blanket theoretical characterizations of OT and CRDT algorithms is exactly the kind of folly that the article is trying to address. For example, it's a logical contradiction to begin the statement with "OT's complexity is _generally_ governed by editing history (H), i.e. O(H)" to conclude that "CRDTs have much better perf than OT", then adding a qualification that argument applies only for the specific off…

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

DOI 10.1145/2957276.2957300 is an attempt at using binary-tree variants to improve CRDT's searching performance bottleneck in converting external index position to internal object identifiers. We address these specific complexities in Section 4.2.1.

DOI 10.1145/2957276.2957300 doesn't deal with operation compression. If you believe it does, please point out where we might find it.

It is trivial state opinions like 'OT is complex', but much harder work to back it up with concrete evidence. I'd think folks will find the discussion more informative without the constant hand-waving.

Re: Real Differences Between OT and CRDT for Co-Editors

#64

Post by zawirski »

nused wrote: post #63
marc_shapiro wrote: post #62

Earlier quoted context omitted.

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

DOI 10.1145/2957276.2957300 is an attempt at using binary-tree variants to improve CRDT's searching performance bottleneck in converting external index position to internal object identifiers. We address these specific complexities in Section 4.2.1. DOI 10.1145/2957276.2957300 doesn't deal with operation compression. If you believe it does, please point out where we might find it. It is trivial state opinions like 'O…

Have you submitted the paper to a peer-reviewed venue? I've read the arXiv version already, and I'd be more than happy to volunteer reviewing it if that's not too late.

Re: Real Differences Between OT and CRDT for Co-Editors

#65

Post by nused »

zawirski wrote: post #64
nused wrote: post #63

Earlier quoted context omitted.

DOI 10.1145/2957276.2957300 is an attempt at using binary-tree variants to improve CRDT's searching performance bottleneck in converting external index position to internal object identifiers. We address these specific complexities in Section 4.2.1. DOI 10.1145/2957276.2957300 doesn't deal with operation compression. If you believe it does, please point out where we might find it. It is trivial state opinions like 'O…

Have you submitted the paper to a peer-reviewed venue? I've read the arXiv version already, and I'd be more than happy to volunteer reviewing it if that's not too late.

It appears you have specific comments and/or feedback? Either post them on HN or send them to the primary contact's email. Either way, we'll make an earnest effort to respond.

This discussion is of interest to folks both inside and outside of academia and the developer community brings valuable hands-on experiences to the table. So, let's keep it inclusive.

Re: Real Differences Between OT and CRDT for Co-Editors

#66

Post by zawirski »

nused wrote: post #65
zawirski wrote: post #64

Earlier quoted context omitted.

Have you submitted the paper to a peer-reviewed venue? I've read the arXiv version already, and I'd be more than happy to volunteer reviewing it if that's not too late.

It appears you have specific comments and/or feedback? Either post them on HN or send them to the primary contact's email. Either way, we'll make an earnest effort to respond. This discussion is of interest to folks both inside and outside of academia and the developer community brings valuable hands-on experiences to the table. So, let's keep it inclusive.

Let me prioritize the usual academic processes first to make sure the outcomes are more persistent and visible, given we are talking about a publication under review or a draft. I will reach out to the paper's primary contact.
Post reply on HN