5 ms·

That is nice! A couple of questions: Do you have released a CT implementation in top of Chronofold? Have you any plans to benchmark it against other algs?

gritzko 5y ago
Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2]. [1]: http://doc.replicated.cc/%5EWiki/ron.sm http://doc.replicated.cc/%5EWiki/ron.sm [2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599814975 https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...
- omgtehlion 5y ago
  Thanks! I googled only 1 impl in Rust: https://github.com/dkellner/chronofold https://github.com/dkellner/chronofold which seems to produce invalid results on some inputs. Actually the hard part (integration) is made of hacks there... That PoC Wiki sounds really interesting and the whole replicated.cc project! Any plans on releasing it?
  - gritzko 5y ago
    Here is Kotlin https://github.com/decentralized-hse/collab-edit https://github.com/decentralized-hse/collab-edit libron will be released, yes.
  - dkellner_ 5y ago
    May I ask which inputs produced invalid results for you and which parts you consider hacky? I'd very much like to improve the implementation, so a reply here or an issue on e.g. GitHub would be highly appreciated. Thanks!
    - omgtehlion 5y ago
      Wow, thanks for reply! Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the merging strategy verbatim from it, and it passed all the tests in repo plus some additional tests. But when faced a real user input strange things happened. I will try to find exact cases and open an issue, but not today, unfortunately :( Edit: AFAIR, I had problems with this func: https://github.com/dkellner/chronofold/blob/16773193b2d21f814d322bec602d3c2e0bebb64b/src/iter.rs#L140 https://github.com/dkellner/chronofold/blob/16773193b2d21f81... and the problem manifested itself for concurrent deletes. Plus it has reversed order for consecutive deletes regarding to original paper. I have not succeeded with fixing it and just scratched the whole thing and used a simpler (yet not as performant) merging strategy...
      - dkellner_ 5y ago
        Don't worry, your details already help a lot! I will look into it later this week. The published version indeed has one bug regarding inserts referencing a deleted element. Maybe that is (part of) what you saw as well. I've fixed that locally already, but unfortunately only after I've made signifant other changes which are still to be refactored & published ;-). Probably time to just backport the fix and release it.
        dkellner_ 5y ago
        Well, that was a productive lunch break ;-). I've just published version 0.2.1, fixing the bug mentioned above.

gritzko 5y ago

Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2]. [1]: http://doc.replicated.cc/%5EWiki/ron.sm http://doc.replicated.cc/%5EWiki/ron.sm [2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599814975 https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...

omgtehlion 5y ago
Thanks! I googled only 1 impl in Rust: https://github.com/dkellner/chronofold https://github.com/dkellner/chronofold which seems to produce invalid results on some inputs. Actually the hard part (integration) is made of hacks there... That PoC Wiki sounds really interesting and the whole replicated.cc project! Any plans on releasing it?
- gritzko 5y ago
  Here is Kotlin https://github.com/decentralized-hse/collab-edit https://github.com/decentralized-hse/collab-edit libron will be released, yes.
- dkellner_ 5y ago
  May I ask which inputs produced invalid results for you and which parts you consider hacky? I'd very much like to improve the implementation, so a reply here or an issue on e.g. GitHub would be highly appreciated. Thanks!
  - omgtehlion 5y ago
    Wow, thanks for reply! Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the merging strategy verbatim from it, and it passed all the tests in repo plus some additional tests. But when faced a real user input strange things happened. I will try to find exact cases and open an issue, but not today, unfortunately :( Edit: AFAIR, I had problems with this func: https://github.com/dkellner/chronofold/blob/16773193b2d21f814d322bec602d3c2e0bebb64b/src/iter.rs#L140 https://github.com/dkellner/chronofold/blob/16773193b2d21f81... and the problem manifested itself for concurrent deletes. Plus it has reversed order for consecutive deletes regarding to original paper. I have not succeeded with fixing it and just scratched the whole thing and used a simpler (yet not as performant) merging strategy...
    - dkellner_ 5y ago
      Don't worry, your details already help a lot! I will look into it later this week. The published version indeed has one bug regarding inserts referencing a deleted element. Maybe that is (part of) what you saw as well. I've fixed that locally already, but unfortunately only after I've made signifant other changes which are still to be refactored & published ;-). Probably time to just backport the fix and release it.
      - dkellner_ 5y ago
        Well, that was a productive lunch break ;-). I've just published version 0.2.1, fixing the bug mentioned above.