lab notes
I've now implemented an Op-based and a Pure op-based CRDT. I couldn't quite make the leap before to merkle-based CRDTs. While vectors clocks are mechanically simple, I wasn't quite sure how they mapped to a merkle-DAG node if replica IDs weren't available.
lab notes
This continues my exploration into CRDTs, beyond the typical tutorials. The more I looked, the more threads there were to pull on. I currently have a couple of lines of questioning to answer: * How do we compose CRDTs so they both converge to a single state without coordination but with
lab notes
After the implementation of the Prolly Tree, I set about writing an immutable map. It was pretty straightforward as most of the heavy lifting is done by the Prolly Tree implementation. The immutable map just keeps a simple list of roots after every change. There are a bunch of improvements
lab notes
It took a long time, but the incremental insert for a Prolly Tree is finally done. I don't think I've ever spent this long as such a little part of code. The two aspects that had me struggling were the bottom-up breadth-first traversal, and how to
lab notes
The punchline first: the incremental insert is finally done on the Prolly Tree. I don't think I've ever spent so much time on such a small, core piece of code. It was also a lesson for me to lean into the struggle and talk about it.
lab notes
A problem was that traversal in a layer would be backward. I'd need to traverse left-to-right to match the build process when building the Prolly Tree from scratch. No problem, I'll just loop through the children backward when processing top-down.
QnA
❓What is this? LinkedIn sometimes suggests that I take an unpaid gig as an advice columnist. Here, I take them up on it, especially if my answers run contrary to typical answers.It's easy to fall into the trap of Seeing like a State [https://www.ribbonfarm.com/
lab notes
I've been stuck on the incremental insertion of a key in a Prolly Tree, and feeling like I'm in a bog. The version where a Prolly Tree is built from scratch was relatively straightforward. I was able to write it in a day. The incremental version
lab notes
Last week, I built Prolly Trees from scratch and probed some of its properties. This week, I started building a Prolly Tree incrementally, by inserting one key at a time. It was more challenging than I suspected at first glance, seeing as I implemented it three times. In a typical
lab notes
Alright, party people. This week I went back to reimplementing Prolly Trees. I wanted to finish out the Lattice Merkle Tree. But given that my goals aren't to just fiddle around in applied research and Prolly Trees already work, I reimplemented Prolly Trees from scratch. I was delighted
techno-optimism
Recently, the Rabbit r1 launched. It's a new handheld device that promises a new primary interaction model with compute: by talking to them in the context of the real world. In turn, they would help us perform actions to help us with unstructured, but menial tasks throughout our
programming
👉When I had mistakenly thought that Prolly Trees weren't uncit, I thought maybe an interesting way forward was to leverage the same mechanism CRDTs use to converge. Below is a mathematical description of what I called a Lattice Merkle Tree, still incomplete. I had time-boxed this, so I