Mutual Search

Details Mutual Search Mutual Search

1999-02-02

arxiv.org/abs/cs/9902005v1

Computer Science

Data Structures and Algorithms

18 pages, Latex, 5 figures, J. Assoc. Comp. Mach., To appear

Scientific paper

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 suffice and $0.536n$ queries are required; in the asynchronous case $0.896n$ queries suffice and a fortiori 0.536 queries are required; for $o(\sqrt{n})$ \agents using a 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 randomized protocols require at least $0.125n$ worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Mutual Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Mutual Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mutual Search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-457972