Parsimonious flooding in geometric random-walks

• We analyze parsimonious-flooding on MANETs yielded by random-walks.
• We provide analytical bounds on its completion time. Such bounds are optimal for a wide range of the inputs.
• Departing from previous analysis, our technique determines the dynamic shape of the information-spreading process.

We study the epidemic process yielded by the k-Flooding Protocol in geometric Mobile Ad-Hoc Networks. We consider n agents on a square performing independent random walks. At any time step, every active agent informs every non-informed agent which is within distance R from it. An informed agent is active only for k time steps. Initially, a source agent is informed and we look at the completion time of the protocol. We prove optimal bounds on the completion time of the process. Our method of analysis provides a clear picture of the geometric shape of the information spreading over the time.