  A gossip protocol is a procedure for spreading secrets among a group of
agents, using a connection graph. The goal is for all agents to get to know all
secrets, in which case we call the execution of the protocol successful. We
consider distributed and dynamic gossip protocols. In distributed gossip the
agents themselves instead of a global scheduler determine whom to call. In
dynamic gossip not only secrets are exchanged but also telephone numbers (agent
identities). This results in increased graph connectivity. We define six such
distributed dynamic gossip protocols, and we characterize them in terms of the
topology of the graphs on which they are successful, wherein we distinguish
strong success (the protocol always terminates, possibly assuming fair
scheduling) from weak success (the protocol sometimes terminates). For five of
these protocols strong (fair) and weak success are characterized by weakly
connected graphs. This result is surprising because the protocols are fairly
different. In the sixth protocol an agent may only call another agent if it
does not know the other agent's secret. Strong success for this protocol is
characterized by graphs for which the set of non-terminal nodes is strongly
connected. Weak success for this protocol is characterized by weakly connected
graphs satisfying further topological constraints that we define in the paper.
One direction of this characterization is surprisingly harder to prove than the
other results in this contribution.
