Strategies for distributed search

ABSTRACT

The problem of locating information among cooperating agents within a distributed computing environment is considered. Such collections of agents can be collectively thought of as a single distributed application providing a single set of services; the X.500 distributed directory is an example of such an application. A central problem in such applications is the cooperative search for certain information which might be located at one of the agents. One approach to this problem relies on flooding messages throughout the distributed environment, such as that which might be used in routing algorithms to locate entries. Although the use of such algorithms, in principle, takes advantage of reaching many different agents via parallel data communication paths, the additional number of messages may be a distinct disadvantage in “higher layer” applications. This paper presents a variant of such approaches which rely on a depth-first method of distributing messages. Results of simulations illustrating the savings in messages of this approach to one relying on traditional flooding are presented for different network configurations.

REFERENCES

• 1: A. Baratz, I. Gopal, and A. Segall. Fault Tolerant Queries in computer Networks. Distributed Computing, Springer-Verlag. Lecture Notes in Computer Science, No. 385, pp 33-45, 1988.
• 2: M. A. Bauer, Richard A. McBride, and J. Michael Bennett. Distributed Search for Cooperative Applications. Technical Report 296, Department of Computer Science, The University of Western Ontario, London, Ontario, August, 1990.
• 3: M. A. Bauer. Naming and Name Management Systems: A Survey of the state of the art. Technical Report 241, Dept. of Computer Science, The University of Western Ontario, London, Ontario, May 1989.
• 4: CCITT. X.500 Directory Service. CCITT, 1987.
• 5: Larry L. Peterson, The profile naming service, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.341-364, Nov. 1988 [doi>10.1145/48012.48013]
• 6: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 7: T. Wang. Algorithms for Distributed Search. M.Sc. Thesis, Department of Computer Science, The University of Western Ontario, London, Ontario, August, 1991.
• 8: P. Bradd, T. Zmetana. XDSS: A Simulation Tool for Investigating Hunting Algorithms. Fourth-year Thesis, Department of Computer Science, The University of Western Ontario, London, Ontario, August, 1991.
• 9: M. F. Schwartz. The Networked Resource Discovery Project. Proceedings IFIP XI World Congress, pp 33-45, San Francisco, CA, Aug. 1989.
• 10: M. F. Schwartz, P. G. Tsirigotis. Techniques for Supporting Wide Area Distributed Applications. Technical Report CU-CS-519-91, Department of Computer Science, The University of Colorado at Boulder, Boulder, Colorado, February, 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Experimentation, Measurement, Performance