  Broadcast and consensus are most fundamental tasks in distributed computing.
These tasks are particularly challenging in dynamic networks where
communication across the network links may be unreliable, e.g., due to mobility
or failures. Indeed, over the last years, researchers have derived several
impossibility results and high time complexity lower bounds (i.e., linear in
the number of nodes $n$) for these tasks, even for oblivious message
adversaries where communication networks are rooted trees. However, such
deterministic adversarial models may be overly conservative, as many processes
in real-world settings are stochastic in nature rather than worst case.
  This paper initiates the study of broadcast and consensus on stochastic
dynamic networks, introducing a randomized oblivious message adversary. Our
model is reminiscent of the SI model in epidemics, however, revolving around
trees (which renders the analysis harder due to the apparent lack of
independence). In particular, we show that if information dissemination occurs
along random rooted trees, broadcast and consensus complete fast with high
probability, namely in logarithmic time. Our analysis proves the independence
of a key variable, which enables a formal understanding of the dissemination
process.
  More formally, for a network with $n$ nodes, we first consider the completely
random case where in each round the communication network is chosen uniformly
at random among rooted trees. We then introduce the notion of randomized
oblivious message adversary, where in each round, an adversary can choose $k$
edges to appear in the communication network, and then a rooted tree is chosen
uniformly at random among the set of all rooted trees that include these edges.
We show that broadcast completes in $O(k+\log n)$ rounds, and that this it is
also the case for consensus as long as $k \le 0.1n$.
