In the Gnutella P2P protocol, searches are broadcast to the nearest neighbors in the (essentially random) graph (with a hop count to prevent infinite propagatio

In the Gnutella P2P protocol, searches are broadcast to the nearest neighbors in the (essentially random) graph (with a hop count to prevent infinite propagation, and keeping a list of recently seen query IDs to prevent cycles). This essentially causes a random graph with N-ary nodes to act like a tree with a branching factor of N-1. Think of it as running the spanning tree algorithm[0] for each query. (The Nth link is the link up to the parent of the node. This analysis ignores duplicate links.) Peers exchange Bloom filters of the keywords for the files they have. That way, if the hop count indicates that a query has only one more hop to live, the Bloom filters are consulted to eliminate the last hop in cases where a leaf node doesn't have any matching files. (Since Bloom filters don't have false negatives, this pruning is safe/conservative.) It might not sound like much to only save the last hop, but remember that for a tree of degree N-1, the leaves represent almost (N-2)/(N-1) portion of the nodes. So, if every peer is connected to 21 other peers, you get a 20-way tree, and a bloom filter at best can save you almost 95% of your query traffic. There's lots of simplification in the above analysis (ignoring multiple paths to the same host, etc., etc.) but you get the gist of it. (This assumes a query for some really rare keyword... the peers use sampling of their nearest neighbors to first estimate the hop count they need in order to get a target number of search results... so searches for popular keywords are unlikely to be helped by the Bloom filter, but they're also sent with a low hop count.) [0]https://en.wikipedia.org/wiki/Spanning_Tree_Protocol https://en.wikipedia.org/wiki/Spanning_Tree_Protocol