Paper Info
Title
Mutual search
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.586n queries are required; in the asynchronous case 0.896n queries suffice and a fortiori 0.536n queries are required; for on 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.5n queries and all radomized protocols require at least 0.25n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.
Year
DOI
Venue
1999
10.1145/320211.320232
Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms
Keywords
DocType
Volume
distributed computation,synchronous case,worst-case expected query,deterministic protocol,following worst-case result,n queries suffice,nonoblivious setting,discrete algorithms,mutual search,queries suffice,n site,asynchronous case,computer networks,computational complexity,coalition forming,datastructures
Journal
cs.DS/9902005
Issue
ISBN
Citations 
4
0-89871-410-9
7
PageRank 
References 
Authors
0.75
11
6
Name
Order
Citations
PageRank
Harry Buhrman11607117.99
Matthew Franklin24570310.44
Juan A. Garay32785222.49
Jaap-Henk Hoepman446053.96
John Tromp571.08
Paul Vitányi62130287.76