Technical Report CIS-2000-03

TR#:CIS-2000-03
Class:CIS
Title: ANTS: Agents on Networks, Trees, and Subgraphs
Authors: Israel A. Wagner, Michael Lindenbaum and Alfred M. Bruckstein
PDFCIS-2000-03.pdf
Abstract: Efficient exploration of large networks is a central issue in data mining and network maintenance applications. In most existing work there is a distinction between the active ``searcher'' which both executes the algorithm and holds the memory and the passive ``searched graph'' over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and t he links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which a non-centralized group of one or more lightweight autonomous agents traverse the network in a completely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and reduced load on the busy nodes due to the small amount of memory and computing resources required by the agent in each node. Algorithms for network covering based on this paradigm could be used in today's Internet as a support for data mining and network control algorithms. Recently, a "Vertex Ant Walk" (VAW) method has been suggested for search ing an undirected, connected graph by an a(ge)nt that walks along the edges of the graph, occasionally leaving ``pheromone'' traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd where n is the number of vertices and d the diameter of the graph. In this work we further investigate the performance of the VAW method on dynamic graphs, where edges may appear or disappear during the search process. In particular we prove that (a) if a certain spanning subgraph S is stable during the period of covering, then the VAW method is guaranteed to cover the graph within time nd_{s}, where d_{s} is the diameter of S, and (b) if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd log((D)log (1/p) + (1+p)(1-p)), where D is the maximum vertex degree in the graph. We also show that (c) if G is a static tree then it is covered within time 2n.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2000/CIS/CIS-2000-03), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2000
To the main CS technical reports page

Computer science department, Technion