title: Coverage maximization under resource constraints using a nonuniform proliferating random walk.
abstract: Information management services on networks, such as search and dissemination, play a key role in any large-scale distributed system. One of the most desirable features of these services is the maximization of the coverage, i.e., the number of distinctly visited nodes under constraints of network resources as well as time. However, redundant visits of nodes by different message packets (modeled, e.g., as walkers) initiated by the underlying algorithms for these services cause wastage of network resources. In this work, using results from analytical studies done in the past on a K-random-walk-based algorithm, we identify that redundancy quickly increases with an increase in the density of the walkers. Based on this postulate, we design a very simple distributed algorithm which dynamically estimates the density of the walkers and thereby carefully proliferates walkers in sparse regions. We use extensive computer simulations to test our algorithm in various kinds of network topologies whereby we find it to be performing particularly well in networks that are highly clustered as well as sparse.
authors.affiliation: Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur 721302, India.
authors.forename: Sudipta
authors.initials: S
authors.lastname: Saha
authors.forename: Niloy
authors.initials: N
authors.lastname: Ganguly
mesh_terms: D003195:Computer Communication Networks; D003198:Computer Simulation; D016247:Information Storage and Retrieval / Q000379:methods*; D015233:Models, Statistical; D012815:Signal Processing, Computer-Assisted