AljoschaMeyer
commented
1 year ago 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
kin the "k-ary search process" over the wire.
b5
Hi @b5 , this is the author of the range-based set reconciliation paper. Sorry about the odd choice of communication channel, but github was the only platform I could find where we both have accounts.
I saw your video summary of the paper, thank you for putting in the effort (and improving over the spartan tikz figures). I'm excited to see people considering this work, earthstar is another project that builds upon it. If you have any questions about the paper contents or beyond, I can probably make time for some synchronous or asynchronous communication. Feel free to contact me via email at researchataljoscha-meyerdotde. Also, feel free to delete this blatant misuse of the issue tracker.
Cheers, Aljoscha