search

ottypes / json1

This is an operational transform type replacement for ottypes/json0
314 stars 27 forks source link

Theoretical Foundations for Contributions #3

Open gaurav21r opened 8 years ago

gaurav21r commented 8 years ago

As per my understanding ShareJS is a full collaboration system, complete with Transformation Functions and the Networking algorithm.

ottypes like json0 and json1 are the transformation function themselves extracted out of ShareJS?

So these are basically algorithms? I'd really like my team & I to contribute to these projects. We are literate is JS / TS / CofeeScript / ES6 etc. but in order to contribute to an algorithmic project such as this what can be some reference material?

Are the algorithms being used here out of one or more specific research papers?

Are there general OT algorithms in the wild? Other implementations / Academic study / research papers?

Are you creating your own algorithm here? If so, can you specify some mathematical / theoretical foundation?

It would be great if you could revert for json1 and ottypes/json0

josephg commented 8 years ago

Great questions. Yes, thats the general idea.

The algorithms are originally based on the work of the google wave team, which in turn were based on the Jupiter collaboration system paper from 1995. All quite old stuff academically - although there's been a lot of tweaks and changes.

Speaking of papers, I read a really disappointing paper about OT a year or two ago. In it OT algorithms were benchmarked against CRDTs and they did very poorly. It was disappointing because the performance of the OT system in the paper had an abysmally poor implementation. Simple tweaks like allowing operation composition were so obviously missing.

I'm sure there's a paper or two which could be written based on the implementations of all this stuff - but I've got no idea what would be considered novel / interesting to the academic community. (And I'm not embedded in that culture. I can't afford to go to conferences out of my own pocket.)

ShareJS was made with the idea that a system to do OT really doesn't care what the operations & documents look like, so long as they have a consistent API. Wave had a problem where we wanted to allow collaborative editing of different data types inside a wave, but all waves did OT with an XML-like rich text structure, and that didn't translate well to unsorted maps and sets. So instead of building other data structures on top of a single OT implementation, sharejs lets you define custom semantics however you like.

The algorithms in the ottypes were extracted out of sharejs, but they were always intended to be separate from sharejs. They just lived in sharejs at first to make it easy to iterate on their API.

If you want some reference on how they're used, understanding the code in this project is a great place to start.

As for help - um, I'd love to have some people to discuss the new json type with. There's still some open questions (like exactly how we should deal with conflicts). Maybe we should make a mailing list or something?

green-coder commented 7 years ago

Hi, I am very interested by json1 too, I would like to build a collaborative Scratch-like where the data is made of json object trees. Json0 won't be good enough for the long term because users often move blocks from one location in a tree to another, they might loose some data and that might frustrate them.

Feel free to discuss with me, but I am more or less a novice at OT (I didn't implement shareJS :p).

serle commented 6 years ago

Hi, I've just hit the need to add OT into my project could you give another update to the status of this implementation. I'm going to review your AppState project as I want to implement OT in conjunction with my existing Apollo GraphQL cache.