Resource finding in store-and-forward networks |
| |
Authors: | José M Bernabéu-Aubán Mustaque Ahamad Mostafa H Ammar |
| |
Affiliation: | (1) Departamento de Sistemas Informaticos y Computación, Universidad Politécnica de Valencia, Apartado 22012, E-46071 Valencia, Spain;(2) College of Computing, Georgia Institute of Technology, 30332 Atlanta, GA, USA |
| |
Abstract: | We present a model of searching for a resource in a distributed system whose nodes are connected through a store-and-forward network. Based on this model, we show a lower bound on the number of messages needed to find a resource when nothing is known about the nodes that have the current location of the resource. The model also helps us to establish results about the time complexity of determining a message optimal resource finding algorithm when the probability distribution for the location of the resource in the network is known. We show that the optimization problem is NP-hard for general networks. Finally we show that optimal resource finding algorithms can be determined in polynomial time for a class of tree networks and bidirectional rings. The polynomial algorithms can be used as a basis of heuristic algorithms for general networks.This work was supported in part by NSF grants CCR-8806358 and NCR-8604850 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|