irwt

Thanks for the links. I will read them during the upcoming days and hopefully find some time to write a blog or something. This looks pretty cool.

Excellent question. I did not address this in the paper, but I probably should have. The upper-bound you mentioned technically does not happen directly because of the nodes, but because of the increased "rate of events" (which can either happen because of the increase of nodes, or because already existing nodes suddenly create more events). Depending on m and k, there will be a rate of events that will cause things to mess up. I'm still brainstorming about this, but I believe we could fix this issue if we'd use a scalable counting bloom filter (https://haslab.uminho.pt/cbm/files/dbloom.pdf), instead of a normal counting bloom filter.

Very good question. I will have to think about it. Will get back to you later.

Imagine that node A and B are in sync (they have the same bloom filter). If A sends a new event to B, B can check if A's new event really results in that new bloom filter. You basically have a cryptographic proof that an event really happened at that moment. If the hashes of an event point to different indices, you know that something is wrong. Edit: Typo.

Hi everybody. I'm the author of the paper. Let me know if you have any questions or comments.

Author of the paper here. Imagine it like this, if your bloom filter overlaps by a lot an incoming bloom filter, what you can do is go over your logs, find the bloom filter closest by increments to the incoming bloom filter, and then compare them. If the events are not comparable, i.e. concurrent, you will know it immediately. If they are comparable, your false positive rate now will be extremely low (because you picked the bloom filter in your logs that is closest to the one you received).