Set Reconcilliation about iroh.computer

[AljoschaMeyer]

Some quick points on the video:

• 05:25: The thing about using selectors to determine the universe dynamically is that you then also have to rebuild the internal tree data structure that facilitates fingerprint computations according to the choice of universe. A large (although of course not the sole) appeal of the range-based approach is that you do not need to perform a linear-time computation per reconciliation session. I don't mention this in the paper, but you can do certain selections without rebuilding the tree. The key observation is that you can regard a range (start and end) as a very simple form of query. The tree data structure for computing fingerprints that I presented the paper only allows for very simple such queries, but there might be data structures that support more complex ones. One that I know of are higher-dimensional queries (e.g., "all cars with length between 3 and 5 meters, built between 1983 and 2014"), which can be efficiently supported by using a k-d-tree internally. There might be others as well (although I'm not particularly optimistic about that), but higher-dimensional ranges already allow for quite a few use cases (I have little idea about the ipfs-adjacent problem spaces though).
• 11:35: Not only does Alice not get a response, she also knows she won't get a response - no message part that she sent can elicit a response. There is no limbo of being unsure whether Bob disconnected or has finished reconciling.
• 12:25: Neither the tree of messages over the wire nor the internal tree data structure are restricted to being binary trees. For the messages, there's simply no need to restrict it to binary trees - in the recursion step, you can split into an arbitrary number of sub-ranges. The only requirement is that at least two of the sub-ranges are nonempty, to ensure progress. The branching factor can be used to interpolate between the total number of roundtrips in the overall bandwith consumption; this choice can even be made dynamically to adapt to current load. For the internal tree data structure, the degree can be freely chosen as well - that's one of the main reasons you need those scary monoids (not to be confused with the monads of Haskell fame; those are more complex than the fluffy, gentle monoids). So you can use an efficient construction like a B-tree internally. And this choice has no effect on the choice(s) of k in the "k-ary search process" over the wire.

[b5]

👋 @AljoschaMeyer! I'm delighted to see that Gihub is our platform-in-common 😄.

Thank you so much for pointing out earthstar, and even more so for your detailed replies to specific points. Do you mind if I add your replies as a comment on the video itself & cite you? It'd be great to keep these notes in place others can find them.

I'd love to find some time to chat, and will reach out via your email address.

Thanks!
Brendan