4 ms·

Interesting! I'm thinking even polynomial methods can "fail" if you underestimated the difference didn't send a big enough sketch. Won't you have to do some s

Interesting! I'm thinking even polynomial methods can "fail" if you underestimated the difference didn't send a big enough sketch. Won't you have to do some sort of exponential fallback anyway to cover that case? If so, you could also use a lower overhead in the IBT and just rely on the same fallback mechanism.

nullc 6y ago
Depending on your communications cost model there is no reason to use an exponential backoff with pinsketch: you can just send one (or N) more sketch-entries at a time. At a cost of one or two extra entries total, you can tell if you have enough before doing the costly computation. [There are some utility functions in minisketch that tell you how much overhead you need to make all failures fast-detectable with a cryptographic level of certainty, it's typically a tiny amount] Your application may also know by construction that the symmetric difference won't be larger than expected. This is the case for e.g. biometric key generation-- if the difference larger than expected it just means the auth failed. Likewise for using pinsketch for anonymous communication. If you notice on our graphs IBLT never gets to particularly low overhead-- at least for small keys, even when you accept low reliability. Efficient fallback also doesn't work quite as well for iblt: For pinsketch when the sketch is too small you can send more entries (a shorter sketch is just a prefix of a longer sketch), which is perfectly efficient (+/- rtt costs). You can also bisect the sketch by splitting into two sketches with an arbitrary hash function and conserve your prior communication: you send the sketch of just the left half and the receiver can get the sketch of the right half by xoring the left with the parent sketch. Bisection has communications overhead because splitting will not distribute items perfectly equally. For pinsketch the only reason you'd do the bisection thing instead of extending the sketch is because decoding has O(N^2) computational cost, but for IBLT bisection is the only option on failure other than totally start over with a bigger sketch (and waste all the prior bandwidth). Unfortunately the bisection approach doesn't work as well on IBLT because while pinsketch will be successful in every split segment as soon as that segment is under capacity, IBLT will also continue to fail until the splitting removes all cycles from each segment. So you get inefficiency both from imbalance and from the need to eliminate cycles. Obviously, what trade-offs will make the most sense depends on the application. We've contemplated adding IBLT to minisketch as an option, particularly because the two approaches can be combined in several different ways: e.g. IBLTs where the buckets are small pinsketches just works(tm)) or e.g. when IBLTs fail they often decode most differences but have a few cycles, a small parallel pinsketch can have the known differences removed and resolve the cycles.

nullc 6y ago

Depending on your communications cost model there is no reason to use an exponential backoff with pinsketch: you can just send one (or N) more sketch-entries at a time. At a cost of one or two extra entries total, you can tell if you have enough before doing the costly computation. [There are some utility functions in minisketch that tell you how much overhead you need to make all failures fast-detectable with a cryptographic level of certainty, it's typically a tiny amount] Your application may also know by construction that the symmetric difference won't be larger than expected. This is the case for e.g. biometric key generation-- if the difference larger than expected it just means the auth failed. Likewise for using pinsketch for anonymous communication. If you notice on our graphs IBLT never gets to particularly low overhead-- at least for small keys, even when you accept low reliability. Efficient fallback also doesn't work quite as well for iblt: For pinsketch when the sketch is too small you can send more entries (a shorter sketch is just a prefix of a longer sketch), which is perfectly efficient (+/- rtt costs). You can also bisect the sketch by splitting into two sketches with an arbitrary hash function and conserve your prior communication: you send the sketch of just the left half and the receiver can get the sketch of the right half by xoring the left with the parent sketch. Bisection has communications overhead because splitting will not distribute items perfectly equally. For pinsketch the only reason you'd do the bisection thing instead of extending the sketch is because decoding has O(N^2) computational cost, but for IBLT bisection is the only option on failure other than totally start over with a bigger sketch (and waste all the prior bandwidth). Unfortunately the bisection approach doesn't work as well on IBLT because while pinsketch will be successful in every split segment as soon as that segment is under capacity, IBLT will also continue to fail until the splitting removes all cycles from each segment. So you get inefficiency both from imbalance and from the need to eliminate cycles. Obviously, what trade-offs will make the most sense depends on the application. We've contemplated adding IBLT to minisketch as an option, particularly because the two approaches can be combined in several different ways: e.g. IBLTs where the buckets are small pinsketches just works(tm)) or e.g. when IBLTs fail they often decode most differences but have a few cycles, a small parallel pinsketch can have the known differences removed and resolve the cycles.