Flooding and diameter in weighted random graphs

diluted random graphs. We interpret these weights as delays, and take
them as i.i.d. exponential random variables. We analyze the edge
flooding time defined as the minimum time needed to reach all nodes
from one uniformly chosen node, and the edge diameter corresponding to
the worst case edge flooding time. Under some regularity conditions on
the degree sequence of the random graph, we show that these quantities
grow as the logarithm of n, when the size of the graph n tends to
infinity. We also drive the exact value for the prefactors.

These results allow us to analyze a randomized broadcast algorithm in
continuous time for random regular graphs. Surprisingly, the
continuous time version of the algorithm performs better than its
synchronized version. We show that this counter-intuitive fact is due to the variability of the exponential.