  In this paper, we study the question of how efficiently a collection of
interconnected nodes can perform a global computation in the widely studied
GOSSIP model of communication. In this model, nodes do not know the global
topology of the network, and they may only initiate contact with a single
neighbor in each round. This model contrasts with the much less restrictive
LOCAL model, where a node may simultaneously communicate with all of its
neighbors in a single round. A basic question in this setting is how many
rounds of communication are required for the information dissemination problem,
in which each node has some piece of information and is required to collect all
others. In this paper, we give an algorithm that solves the information
dissemination problem in at most $O(D+\text{polylog}{(n)})$ rounds in a network
of diameter $D$, withno dependence on the conductance. This is at most an
additive polylogarithmic factor from the trivial lower bound of $D$, which
applies even in the LOCAL model. In fact, we prove that something stronger is
true: any algorithm that requires $T$ rounds in the LOCAL model can be
simulated in $O(T +\mathrm{polylog}(n))$ rounds in the GOSSIP model. We thus
prove that these two models of distributed computation are essentially
equivalent.
