You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
7.2. Efficient Gossip with Bloom Filters
To send messages to peers that are not directly connected, BitChat employs a "flooding" or "gossip" protocol. When a peer receives a packet that is not destined for it, it acts as a relay. To prevent infinite routing loops and minimize memory usage, the protocol uses an OptimizedBloomFilter to track recently seen packet IDs.
The logic is as follows:
A peer receives a packet.
It checks the Bloom filter to see if the packet's ID has likely been seen before. If so, the packet is discarded. Bloom filters can have false positives (though they are rare), but they guarantee no false negatives. This means a new packet will never be accidentally discarded.
If the packet is new, its ID is added to the Bloom filter.
The peer decrements the packet's Time-To-Live (TTL) field.
If the TTL is greater than zero, the peer re-broadcasts the packet to all of its connected peers, except for the peer from which it received the packet.
This mechanism allows packets to "flood" through the network efficiently, maximizing the chance of reaching their destination while using minimal resources to prevent loops.
A bloom filter detects items that are already inserted into it, so if an item is already inserted the bloom filter will always return true for this item query.
And for non seen items it will return false most of the times and rarely return true.
When taking a new message id and querying the bloom filter with it we have a small chance of getting a true negative (the bloom filter thinks it already seen it)
And in the whitepaper text it says "This means a new packet will never be accidentally discarded."
But as explained when the bloom filter says the message is already seen the node will discard it.
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
-
Here is the problematic text:
A bloom filter detects items that are already inserted into it, so if an item is already inserted the bloom filter will always return true for this item query.
And for non seen items it will return false most of the times and rarely return true.
When taking a new message id and querying the bloom filter with it we have a small chance of getting a true negative (the bloom filter thinks it already seen it)
And in the whitepaper text it says "This means a new packet will never be accidentally discarded."
But as explained when the bloom filter says the message is already seen the node will discard it.
Beta Was this translation helpful? Give feedback.
All reactions