Local-first Conf 2025

We are in the middle of the second Local-first Conf (May 26 – 28), 2025. Just keeping track here of ideas worth a follow up.

Is IPFS dead?

I personally love CAS (content addressable storage) and IPFS seems like the best distributed transport for CAS we have. I don’t see any other better alternatives to CAS for building distributed apps. IMO, CAS is by far the best storage to build distributed apps on top of, better than any other P2P tech I have seen.

However, it looks like the general sentiment at the conference (and overall) is that people have given up on IPFS. It is just too slow, too high latency, too unreliable, and too much of a burden to rebroadcast your hashes all the time…

Light in the infinite canvas tunnel

As Excalidraw and Tldraw are for-profit corporations now, I was thinking what could be the next open source infinite canvas editor. (I don’t have time to create one now.) Fortunately, something is happening in this space. There is now OCWG (Open Canvas Working Group), which aims to standardize open canvas storage format, so that there could be one common open source JSON schema capable to represent Figma, Excalidraw, and Tldraw documents. And they even mentioned that they have their own renderer, which renders the OCWG format to an SVG.

Prolly trees for the resque

Prolly trees in CAS (Content Addressable Storage) are even more useful than I though. First, they give you sorted keys (anyone up for SQL implementation?). But it is even better. Guys from dialog-db (a triplet store) mentioned how they use Prolly trees to do a triplet database in CAS. From the root they have three Prolly trees, each tree indexes the different part of the subject-predicate-object triplet. There you go: graph database on top of CAS.

CRDT deep dive

There might be a new way to do the eg-walker merge on concurrent edits, which does not require CRDTs. sdexa brought up this idea where all you need for the merge of concurrent operations is the offset of the insert, no need for any CRDT IDs. This is not verified yet, it might work, but no working implementation exists yet. sdexa looked at this from a very practical perspective: CRDTs are not made for eg-walker merges, so they must carry extra unnecessary information, and that informations turns to be the CRDT character IDs.

I look at this from a bit different perspective, lets think about a common generic way to represent a text insert operation. First lets think how we represent operations in the OT system, it could have three fields:

where, text is the inserted text, and offset is the position from after character. Here after is set to BOF (beginning of file), in OT after is always set to BOF, so we normally do not store it in the operation.

Now, lets see how a typical CRDT operation is represented:

In CRDT it is somewhat in reverse we specify after character ID a.1 (lets say), but the offset is always 0. So, in CRDTs we normally do not communicate the offset field, the offset after after, it is always 0.

But the thing is, actually offset is 0 only during the transmission of the operation. Once the operation is integrated into the sorted list, if there were concurrent edits, the offset might become more than 0. Lets say there was a concurrent edit which inserted also a character after a.1, if that edit is selected to appear before my edit, then, once integrated the offset of my operation is 1 now, because there is this extract character between my insert and the character a.1. Operation transformations happen in CRDTs implicitly, the integration function is the transformation.

So, the WOOT (WithOut Operational Transformation) paper was wrong. They still do the transformation, it is just the offset field during the operation minting is always 0, so it is never explicitly communicated. And during the integration the offset field is potentially incremented, but again, it does not need to be explicitly communicated as the CRDT list order is where that information is stored.

Consider we stored all list RGA (Replicated Growable Array) blocks in a database, each block in a separate SQL row. The table would have these three columns text, offset, after:

Let’s go back to sdexa‘s idea. If his idea works out, what it means is that during the eg-walker merge, we don’t need the after IDs, because during the merge the offset contains enough information. During the time collapse, at that specific time, the offset might be enough. Oh, and I also shall mention that the case sdexa is solving is when there are more than just two branches, he wants to parallelize (run on multiple cores) the eg-walker merge algorithm across branches, as well as being able to arbitrary cut through time.

sdexa is packed with knowledge. He showed me how to find cycles in O(log N) in a tree CRDT. Also, he showed a novel way to support moves in a tree CRDT (and enforcing invariants, in general, not just moves) in a way where you don’t need to store and order operation history to pick one non-cycle-creating move operation (as is currently state-of-the-art). If his approach works, the moves in tree CRDTs could be supported without needing to store the log of operations at all, one would only need to store one latest move operation. Reject all incoming conflicting moves, if they happen. Then pick one of the move operations. If the incoming one is picked, undo that latest move and apply the incoming move.

Even more on CRDTs

Going back to the idea of adding more operations to a list CRDT. I never really figured out how to add move operations, but Michael’s portals might even allow to do more than just moves, also copy and potentially other operations. The place where I was stuck on moves/portals idea for CRDT is I was trying to do them by referencing a range (from this character to that character). But discussing this with Michael, he pointed out that I need to somehow store the “history” or portals (whatever the “history” is), now I think the portals in CRDTs could work, where the history is represented by a reference to the previous portal. So, when you insert a portal into a CRDT, the inserted portal element, instead of being [startId, endId] (referencing the start and end of the CRDT sequence, it must be [startId, startPortalId, endId, endPortalId], where startId and endId are still the start and end characters of the new portal, but startPortalId and endPortalId are references to the old portals from which those characters were picked. This way, recursively, all the portals can be unwrapped to create the view.

OT has these TP1 and TP2 properties. Michael wants to introduce also TP0, which essentially means it should be possible to construct a diff. Now, a cool thing he presented is that in time collapse (aka eg-walker merge), in a two branch scenario (but you can reduce everything to two branches), all you need for the merge is being able to do a diff between the end state of one branch and the other branch. Really cool stuff! So, again, you don’t need a CRDT for the eg-walker time collapse merge.

RGA update operation resurrected

About adding more operations to a list CRDT. When chatting about some deep CRDT internals stuff with Seph and Alex, I remembered that the original RGA (Replicated Growable Array) algorithm also proposed the update operation:

The CRDT implementer community (and, actually, also the research community) largely has completely ignored the update operation. All libraries implement only insert and delete operations. As did json-joy, too. But I suddenly realized that update might be useful, and not for ordered text, but for ordered array elements.

You see json-joy arrays, say [1, 2, 3], also use the RGA algorithm, it is a ordered references-to-other-nodes list. But because only insert and delete operations are available, it is a common practice to wrap the array elements into another val node, which is a LWW register.

What I realized only now, is we would not need that val node wrapping, if only json-joy implemented the update operation. You could update the array element directly, instead of updating the LWW register.