In this talk, we present a decentralized randomized communication scheme called "Spatial Gossip", a scheme with good local and global information dissemination guarantees. We show how Spatial Gossip can be used to design simple protocols for the "Resource Location Problem", in which the nodes of a network are trying to locate the closest copy of a resource (product, machine time, memory, ...). Alternately, we may view gossip not only as a design principle, but as an observable phenomenon, for instance in social networks. The communication mechanism is not under the control of a protocol designer; the task of an algorithm is then to judiciously choose nodes at which to "seed" the communication. In this talk, we present an algorithm that can be shown to select approximately optimal seed node sets.
Along the way, we touch on several other issues, such as how to add the notion of time to graphs in order to reason about information flow, and how the choice of a communication mechanism between nodes affects their ability to perform distributed computations.