Archagon is a developer's blog on CRDTs, collaborative software, Mac apps, and external GPU setups.
HN commenters repeatedly recommend its CRDT article 'Data Laced with History' as a clear, practical explanation compared with academic papers.
> my range tree is just a slightly modified b-tree. But usually when people talk about b-trees they mean a BTreeMap. Thats not what I'm doing here. Instead of storing keys, each internal node of the b-tree stores the total number of characters (recursively) in that item's children. So we can look up any item in the document by character position, or insert or delete anywhere in the document in log(n) time.
Cool! This is essentially the same idea I implemented in 2012; I call it the AList or A-List data structure: http://core.loyc.net/collections/alists-part1
Ever since I made it, I've been looking for a good application for it. I guess this is it! I mean, I knew A-List was a good data structure for text editing, but most applications can use a Gap Buffer which is much simpler. But when it comes to concurrent editing, you've got multiple editing points so a Gap Buffer is suddenly much less attractive.
> Honestly I'm shocked and a little suspicious of how little ram Yjs uses in this test.
It's good, but still it uses ~30x as much RAM as plain string edits. Not surprisingly, you got 3x better memory usage by using A-List and a more efficient language (Rust in this case, but C# and C/C++ can also do well.)
There is a great article about a CRDT concept called "Causal Trees[1]. I wonder how it compares to flat-list-based CRDTs (it's been too long since I researched this).
By the way, Microsoft has a new set of libraries for concurrent editing called Fluid Framework[2]. I'm…
I came across this after seeing relic[0] submitted the other day and thought it was pretty interesting.
I've been into CRDTs for a while and have started wondering about generic mechanisms for distributed data. This lead me to read a lot more about the Relational Model of data and eventually to the Event Calculus.
What's interesting to me is that these things end up feeling a lot like CRDTs[1] or Event Sourcing. I haven't quite finished pulling on these threads but the relic link was a timely read considering!
I really liked the first half of this paper and the Authors categorization of complexity. However the second half fell a bit short for me. It seems they made the same mistake as many other people (SQL != Relational) and their idea of Feeders and Observers seems a bit more like an escape hatch than an elegant method for interfacing with the outside world.
[0] https://github.com/wotbrew/relic
[1] http://archagon.net/blog/2018/03/24/data-laced-with-history/
Good summary of techniques. I'm very interested in this subject matter and really want to get to a formal definition for this architecture of UI. As mentioned in the article, FRP is the closest here and where the techniques initialized from. The patterns deal with how to break down the problem of asynchronous rendering and user interactions (which inherently deals with state changes). The best papers I've read use some Category Theory to show the structure of the flow of certain patterns, and there are also adjacent fields like parallel and concurrent programming that I think are overlapping with this area of how to manage UI state. The recent articles on CRDTs and Causal Trees made me think that could be used not just across a network but to manage the asynchronous state of components.
http://archagon.net/blog/2018/03/24/data-laced-with-history/
It's possible and there has been research in this area, see http://archagon.net/blog/2018/03/24/data-laced-with-history/ for details about conflict resolution.
The main problem is garbage collection - to guarantee that you can sync across all devices for all time, your data structure must be append-only, so your document can only grow. A long living document will eventually grow very very large. You could let the user decide when to collect garbage/establish a new baseline doc; maybe like 5 years. But this means that if you edited the document on a laptop, didn't sync it with another client, and then closed the laptop for 5 years you would lose the ability for the changes you made on that laptop to be resolved automatically.
FWIW, I disagree that it is necessary (or even desirable) to understand the academic basis first.
The core idea of CRDTs are intuitive and easy to understand from an engineering perspective. For me, the academic literature unnecessarily complicates and obscures what's going on, and I would also point newcomers to something like http://archagon.net/blog/2018/03/24/data-laced-with-history/.
It probably has to do with where you are coming from. If you're not a mathematician or theoretical computer scientist, I don't think that reading these documents is going to be a very helpful start.
Good addition! Here are some more:
https://ferd.ca
https://blog.filippo.io
https://lethain.com
http://movingpackets.net
https://www.integralist.co.uk
https://peter.bourgon.org/blog
https://engineering.linkedin.com/blog
https://begriffs.com
https://mijailovic.net
http://tatiyants.com
http://blog.pentestbegins.com (seems down right now?)
https://kalzumeus.com/archive
http://blog.stephenwolfram.com
https://paragonie.com/blog
https://www.filfre.net
https://brandur.org/articles
http://archagon.net
https://eklitzke.org
I guess I could go on forever…