  In this paper, we study PUSH-PULL style rumor spreading algorithms in the
mobile telephone model, a variant of the classical telephone model in which
each node can participate in at most one connection per round; i.e., you can no
longer have multiple nodes pull information from the same source in a single
round. Our model also includes two new parameterized generalizations: (1) the
network topology can undergo a bounded rate of change (for a parameterized rate
that spans from no changes to changes in every round); and (2) in each round,
each node can advertise a bounded amount of information to all of its neighbors
before connection decisions are made (for a parameterized number of bits that
spans from no advertisement to large advertisements). We prove that in the
mobile telephone model with no advertisements and no topology changes,
PUSH-PULL style algorithms perform poorly with respect to a graph's vertex
expansion and graph conductance as compared to the known tight results in the
classical telephone model. We then prove, however, that if nodes are allowed to
advertise a single bit in each round, a natural variation of PUSH-PULL
terminates in time that matches (within logarithmic factors) this strategy's
performance in the classical telephone model---even in the presence of frequent
topology changes. We also analyze how the performance of this algorithm
degrades as the rate of change increases toward the maximum possible amount. We
argue that our model matches well the properties of emerging peer-to-peer
communication standards for mobile devices, and that our efficient PUSH-PULL
variation that leverages small advertisements and adapts well to topology
changes is a good choice for rumor spreading in this increasingly important
setting.
