Thoughts on this? https://hal.archives-ouvertes.fr/inria-00432368/document
Anyone here have experience/ideas about how to implement Peer-to-Peer Collaborative Editing Systems?
1 Like
My thought on this is that it looks like a promising approach and tool for building the collaborative platforms of the future. So, I’ve bookmarked the page. Have only skimmed that paper roughly, but it looks like serious and seriously good stuff!
1 Like
Okay, so, the best way to solve a problem is to avoid it in the first place.
Appoint a Master, send all delta’s to the master. Master is head of a tree structure that distributes the delta’s. Have a “Master is dead” timeout so that you can reappoint a Master.
In this paper, we present a new optimistic replication algorithm called Logoot that ensures CCI consistency for linear structures, that tolerates a large number of copies, and that does not require the use of tombstones. This approach is based on non-mutable and totally ordered object position identifiers.
A tombstone isn’t bad by definition. I think they meant meaningless/empty “lines” - or just anything that lingers. I’m pretty sure there’s lazy syncing ways for removal.
The time complexity of Logoot is only logarithmic according to the document size.
I think a consistency algorithm should be doable in constant time. This is also just not true.
I tried reading the paper but they seriously need to fix their language. 4.2 is seriously confusing. They’re extremely freeform with symbols. Basically this document isn’t even fucking spellchecked.
Damning is the following:
Logoot position identifiers support these constraints since\ their size and space complexity are constant according to peers number (no vector clock). We only assume that each site has a unique identifier.
BAM! Unsatisfiable constraint!
Additionally to position identifiers, Logoot only require a causal dissemination mechanism. To obtain it, a scalable broadcast such as the lightweight probabilistic broadcast [21] in association with causal barriers [22] can be used.
Like, the spelling is so bad, how can this ever be a valid piece of research? Why was there no mention of “causal dissemination mechanism” before? What is it? Why does Logoot need it?
They present some “results”, showing that the alternative algorithms perform… uhh. not at all basically. And that their own algorithm is like, kind of okay but still really awful. They’re hiding the real properties of their algorithm by not performing proper tests, not giving proper complexity analysis, not even giving the algorithm in an understandable way.
I’m sorry but the paper should be forwarded to the toilet.
Isn’t that just clients and a server? It doesn’t scale…?
“tombstones”: a deleted line is
replaced by a tombstone instead of removing it from the document model. In these
approaches, tombstones cannot be directly removed without compromising the document’s
consistency. Therefore, the overhead required to manage the document grows
continuously.
This cost is not acceptable on massive editing systems. For instance, for the the
most edited pages of Wikipedia1 on a tombstone based system, the storage overhead
often represents more than 100 times the document size.
Tombstone are also responsible of performance degradation. Indeed, in all existing
approaches, the execution time of modification integration depends on the whole document
size – including tombstones. Therefore, letting the tombstone number growing
degrades the performance.
That somehow reminds me of the situation of digital currencies before Bitcoin. Switching the master may be an operation that is costly to do. Having fall-back masters in reserve would help, for the price of making the system more complicated.
What problems would a collaborative editing platform on a blockchain suffer from? Blocks would contain deltas. Trustworthiness would be established by reputation that contributors with a specific identity build up.
Only Masters can write, but clients can exchange the information. As long as the master can process all the “please write” requests it scales. You ever hit scaling problems, do paging. Make a “page” at most X bytes long, split the pages and give them different masters. I bet all wikipedia editing could be forwarded through a single master. Scaling seems fine. (note: if a master can’t lead, how could the clients follow? If there’s too many edits for the master there’s probably too many reads for the clients.)
A blockchain approach with proof of work or stake would also work. Just that without the currency the value of a block is pretty low, so there’s not much reason for it. A reputation system (like wiki has), feeding stake to the the proof of stake voting for or against delta’s (or patches) is an improvement, as it prevents vandalism.
Note: preventing vandalism was not even mentioned in the paper. It was merely concerned with being weird about patches.
On could also work with a “Master group”. Any client connects to any master. If a Master wants to make a delta it needs >50% approval from the master group. So, run a consensus algorithm with >50% masters for every delta and you have some half decent anti-vandalism and reliability improvements. Performance is lower, but not much because you need only get approval from >50% of the masters.
Race and repair is also a good option. It shouldn’t be that hard to just pretend you already have consensus, rewind when something went wrong, and replay the user actions if there’s a conflict.
Swarm management should be the difficult part.