Spatial gossip and resource location protocols

The dynamic behavior of a network in which information is chang-ing continuously over time requires robust and efficient mecha-nisms for keeping nodes updated about new information. Gossip protocols are mechanisms for this task in which nodes communi-cate with one another according to some underlying deterministic or randomized algorithm, exchanging information in each commu-nication step. In a variety of contexts, the use of randomization to propagate information has been found to provide better reliability and scalability than more regimented deterministic approaches. In many settings — consider a network of sensors, or a cluster of distributed computing hosts — new information is generated at individual nodes, and is most “interesting ” to nodes that are nearby. Thus, we propose distance-based propagation bounds as a perfor-mance measure for gossip algorithms: a node at distance d fro