Spreading Information with Gossip

Suppose we have a network represented by a graph G=(V,E).  Data ("rumors") 
can be generated at any vertex and these need to be disseminated to all of 
the other vertices.  Rather than having a fixed routing tree we can spread 
the messages by randomly selecting the next vertex to contact.  This 
increases fault tolerance because we are not relying on a fixed path.   In 
this talk I will discuss gossip algorithms for spreading information in 
networks, along with the number of rounds required to spread a message and 
the amount of communication used.  I may also talk about "spatial gossip", 
where we want nodes that are close to the node that generated a message to 
receive the message faster.