Gossip‐based search selection in hybrid peer‐to‐peer networks

We present GAB, a search algorithm for hybrid peer‐to‐peer networks, that is, networks that search using both flooding and a distributed hash table (DHT). GAB uses a gossip‐style algorithm to collect global statistics about document popularity to allow each peer to make intelligent decisions about which search style to use for a given query. Moreover, GAB automatically adapts to changes in the operating environment. Synthetic and trace‐driven simulations show that compared to a simple hybrid approach that always floods first, trying a DHT if too few results are found, GAB reduces the response time by 25–50% and the average query bandwidth cost by 45%, with no loss in recall. GAB scales well, with only a 7% degradation in performance despite a tripling in system size. Copyright © 2007 John Wiley & Sons, Ltd.