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
lab notes
This past week, I'd been working on exploring a new construction for a unicit B+tree. I wanted to know if the mechanisms for uncoordinated synchronization of CRDT could be applied here. Given the research nature of the task, I indulged myself with a limited timebox to the
lab notes
In Lab note #029 [https://interjectedfuture.com/lab-notes/lab-notes-029-balancing-nodes-in-a-unicit-tree/] , I was thinking about a different way to construct a unicit tree. Can we create both a description of the splits in a tree and a comparator that would make it a partially ordered set? And with that partially ordered set
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.For a long time, my impression of LinkedIn as a product was that it was mostly a tool
lab notes
In my previous lab note #028 [https://interjectedfuture.com/lab-notes/lab-note-028-consistent-splitting-for-node-sizes/] , I was worried that Prolly trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees] were not unicit. When I inserted keys in different orders, there was a small chance that splits would propagate to the end
retro review
Compared to 2021 [https://interjectedfuture.com/2021-year-in-review/], I was much more focused this year. Compared to 2022, I have built more conviction. And starting in September, I started to have full days to work, rather than just the nights and weekends. Unlike 2021, I wasn't trying a lot
lab notes
Last time [https://interjectedfuture.com/lab-notes/lab-note-028-consistent-splitting-for-node-sizes/] , I found balancing nodes seemed to be in conflict with the property of a unicit tree. A balanced tree is desirable for efficient queries. A unicit tree is desirable for Merkle Trees for fast equality comparisons. Was there a way to get both?
lab notes
👉See Lab note #30 [https://interjectedfuture.com/lab-notes-030-prolly-trees-are-unicit] for corrections. Prolly Trees are unicit, and don't exhibit the bad behavior I've outlines below.Last week [https://interjectedfuture.com/lab-notes/lab-note-027-breadcrumb-to-prolly-trees/] , I was looking at Prolly Trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#
crdt
đź”°If CRDTs are new to you, here are some introductory links. - An interactive intro to CRDTs [https://jakelazaroff.com/words/an-interactive-intro-to-crdts/] - An introduction to state-based CRDTs [https://www.bartoszsypytkowski.com/the-state-of-a-state-based-crdts/] - CRDTs for non-academics [https://www.youtube.com/watch?v=vBU70EjwGfw] - CRDT: The Hard Parts [https:
lab notes
When I found the splitting of nodes for Merkle Search Trees to be problematic [https://interjectedfuture.com/lab-notes/lab-notes-025-split-condition-for-merkle-search-trees/] , I stumbled upon Prolly Trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees] . They were first described by the Noms, a git for databases [https://github.com/attic-labs/