Gossip in Dynamic Networks

textabstractA gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. In this paper the problem of designing and analyzing gossip protocols is given a dynamic twist by assuming that when a call is established not only secrets are exchanged but also contact list, i.e., links in the gossip graph. Thus, each call in the gossip graph changes both the graph and the distribution of secrets. This paper gives a full characterization for the class of dynamic gossip graphs where the Learn New Secrets protocol (make a call to an agent if you know the number but not the secret of that agent) is successful. 1