Mutual search
Harry Buhrman, Matthew K. Franklin, Juan A. Garay, Jaap-Henk Hoepman, John Tromp, Paul M. B. Vitanyi · Journal of the ACM · 1999
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.