  Consider the classical problem of information dissemination: one (or more)
nodes in a network have some information that they want to distribute to the
remainder of the network. In this paper, we study the cost of information
dissemination in networks where edges have latencies, i.e., sending a message
from one node to another takes some amount of time. We first generalize the
idea of conductance to weighted graphs by defining $\phi_*$ to be the "critical
conductance" and $\ell_*$ to be the "critical latency". One goal of this paper
is to argue that $\phi_*$ characterizes the connectivity of a weighted graph
with latencies in much the same way that conductance characterizes the
connectivity of unweighted graphs.
  We give near tight lower and upper bounds on the problem of information
dissemination, up to polylogarithmic factors. Specifically, we show that in a
graph with (weighted) diameter $D$ (with latencies as weights) and maximum
degree $\Delta$, any information dissemination algorithm requires at least
$\Omega(\min(D+\Delta, \ell_*/\phi_*))$ time % in the worst case. We show
several variants of the lower bound (e.g., for graphs with small diameter,
graphs with small max-degree, etc.) by reduction to a simple combinatorial
game.
  We then give nearly matching algorithms, showing that information
dissemination can be solved in $O(\min((D+\Delta)\log^3{n}, (\ell_*/\phi_*)\log
n)$ time. This is achieved by combining two cases. We show that the classical
push-pull algorithm is (near) optimal when the diameter or the maximum degree
is large. For the case where the diameter and the maximum degree are small, we
give an alternative strategy in which we first discover the latencies and then
use an algorithm for known latencies based on a weighted spanner construction.
(Our algorithms are within polylogarithmic factors of being tight both for
known and unknown latencies.)
