Resource finding in store-and-forward networks (Q758183)

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.