Mutual search Academic Article uri icon

abstract

  • We introduce a search problem called “mutual search” where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form “Anybody at site i ?”. We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols, we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed), there is no savings: n -1 queries are required and are sufficient. In a nonoblivious setting, we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case 0.586 n queries are required; in the asynchronous case 0.896 n queries suffice and a fortiori 0.536 n queries are required; for o(√n) agents using a synchronous deterministic protocol less than n queries suffice; there is a simple randomized protocol for two agents with worst-case expected 0.5 n queries and all radomized protocols require at least 0.25 n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

published proceedings

  • Journal of the ACM

author list (cited authors)

  • Buhrman, H., Franklin, M., Garay, J. A., Hoepman, J., Tromp, J., & Vitnyi, P.

citation count

  • 7

complete list of authors

  • Buhrman, Harry||Franklin, Matthew||Garay, Juan A||Hoepman, Jaap-Henk||Tromp, John||Vitányi, Paul

publication date

  • July 1999