Computer Science – Discrete Mathematics
Scientific paper
2010-07-09
Computer Science
Discrete Mathematics
21 pages, 3 figures --- The results presented in this paper have been extended in: Pettarin et al., Tight Bounds on Informatio
Scientific paper
We study the dynamics of information (or virus) dissemination by $m$ mobile agents performing independent random walks on an $n$-node grid. We formulate our results in terms of two scenarios: broadcasting and gossiping. In the broadcasting scenario, the mobile agents are initially placed uniformly at random among the grid nodes. At time 0, one agent is informed of a rumor and starts a random walk. When an informed agent meets an uninformed agent, the latter becomes informed and starts a new random walk. We study the broadcasting time of the system, that is, the time it takes for all agents to know the rumor. In the gossiping scenario, each agent is given a distinct rumor at time 0 and all agents start random walks. When two agents meet, they share all rumors they are aware of. We study the gossiping time of the system, that is, the time it takes for all agents to know all rumors. We prove that both the broadcasting and the gossiping times are $\tilde\Theta(n/\sqrt{m})$ w.h.p., thus achieving a tight characterization up to logarithmic factors. Previous results for the grid provided bounds which were weaker and only concerned average times. In the context of virus infection, a corollary of our results is that static and dynamically moving agents are infected at about the same speed.
Pettarin Alberto
Pietracaprina Andrea
Pucci Geppino
Upfal Eli
No associations
LandOfFree
Infectious Random Walks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Infectious Random Walks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Infectious Random Walks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-645389