Resource finding in store-and-forward networks
type: Item
instance of: scholarly article
title: Resource finding in store-and-forward networks
zbMATH Open document ID: 0724.68007
DOI: 10.1007/BF01178681
author: José M. Bernabéu-Aubán
author: Mustaque Ahamad
author: Mostafa Ammar
published in: Acta Informatica
publication date: 1991-01-01T00:00:00Z
review text: The paper presents a model of the process of searching for a resource in a distributed system whose nodes are connected through a store-and- forward network. Based on this model, the authors show a lower bound on the number of messages needed to find a resource when nothing is known about the location of the resource. The model also helps to establish some results about the complexity of finding optimal algorithms to locate a resource when the probability distribution for the location of the resource in the network is known. It is also shown that the optimization problem is NP-hard for general networks. Finally, an algorithm for tree networks is presented which can be specialized to polynomial algorithms for special kinds of trees. An application of this algorithm for path networks can be adapted to find optimal search algorithms for bidirectional ring networks.
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4195143
zbMATH Keywords: resource finding
zbMATH Keywords: distributed system
MaRDI profile type: Publication
cites work: Distributed match-making
cites work: Q3833854
cites work: Theory of optimal search
cites work: Optimal Search Using Uninterrupted Contact Investigation
cites work: Optimal Search of a Moving Target
cites work: The complexity of searching a graph
cites work: Q3208679
cites work: Technical Note—The Complexity of the Optimal Searcher Path Problem
full work available at URL: https://doi.org/10.1007/bf01178681
OpenAlex ID: W2100623518
description: scientific article; zbMATH DE number 4195143