Networks are becoming increasingly prominent as a framework for understanding designed or natural phenomena, ranging from decentralized computer systems to social interaction patterns. They serve as a means to facilitate decentralized computation and the dissemination of information. Designing and analyzing their function therefore requires a theory of information flow in networks, building on an understanding of their structure. The goal of such a theory is to help in developing algorithms for core questions, including: How to find a piece of information? How to spread information? How to perform shared computations?
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, ...). We then explore simple gossip-based protocols for other aggregate computations, including averages, moments, random samples, and quantiles of data held by individual nodes in a network.
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.