research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleAnalysis of the Information Propagation Time Among Mobile Hosts
Bibtex cite IDRACTI-RU1-2004-6
Booktitle 3rd International Conference on Ad-Hoc Mobile and Wireless Networks
Series Lecture Notes in Computer Science
Year published 2004
Month July
Volume 3158
Pages 122-134
Publisher Springer Berlin / Heidelberg
Location Vancouver, Canada
DOI 10.1007/b99253
Consider k particles, 1 red and k1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it ldquoinfectsrdquo it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information. In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k1 to the white ones. The infection time Tk of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph. We easily get that an upper bound on the expected value of Tk is the worst case (over all initial positions) expected meeting time m* of two random walks multiplied by THgr (log k). We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the ldquolollipoprdquo graph), a range of values k
Dimitriou, Tassos
Nikoletseas, Sotiris
Spirakis, Paul
fulltext.pdf (main file)
Publication ID212