Locating Information with Uncertainty in Fully Interconnected Networks: The Case of Nondistributed Memory

The problem of searching for a piece of information in a fully interconnected computer network by exploiting advice about its location from the network nodes is discussed. Each node contains a database that knows what kind of documents or information are stored in other nodes. The databases in each node, when queried, provide a pointer that leads to the node that contains the information. It is found that the information is up-to-date with some bounded probability.