Information Dissemination via Random Walks in d-Dimensional Space

Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun and Yajun Wan

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the d-dimensional space {-n, …, n}^d at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al’s work [10], which solved the problem for d = 2. We present tight bounds up to polylogarithmic factors for the case d = 3. (While our results extend to higher dimensions, for space and readability considerations we provide only the case d = 3 here.) Our results show the behavior when d >= 3 is qualitatively different from the case d = 2. In particular, as the ratio between the volume of the space and the number of agents varies, we show an interesting phase transition for three dimensions that does not occur in one or two dimensions.

Guest: Henry Lam
Host: Chen Avin

Parsimonious Flooding in Geometric Random-Walks

Andrea Clementi and Riccardo Silvestri

We study the information spreading yielded by the (Parsimonious) 1-Flooding
Protocol} in geometric Mobile Ad-Hoc Networks. We consider n agents on a convex
plane region of diameter D performing independent random walks with move radius
\rho. At any time step, every active agent $v$ informs every non-informed agent
which is within distance R from v (R>0 is the transmission radius). An agent
is only active at the time step immediately after the one in which has been
informed and, after that, she is removed. At the initial time step, a source
agent is informed and we look at the \emph{completion time} of the protocol,
i.e., the first time step (if any) in which all agents are informed. This random
process is equivalent to the well-known Susceptible-Infective-Removed (SIR)
infection process in Mathematical Epidemiology. No analytical results are
available for this random process over any explicit mobility model. The presence
of removed agents makes this process much more complex than the (standard)
flooding. We prove optimal bounds on the completion time depending on the
parameters n, D, R, and rho. The obtained bounds hold with high probability. We
remark that our method of analysis provides a clear picture of the dynamic shape
of the information spreading (or infection wave) over the time.
end of abstract.
Guest: Andrea Clementi

Host:  Merav Parter