# ICS 269, Spring 1998: Theory Seminar

## 29 May 1998:

Mutual Search

Joseph Wang, ICS, UC
Irvine

We define a new type of search problem called "mutual search",
where *k* players arbitrarily spread over *n* nodes are
required to locate each other by send "Anybody at node I?" query
messages (for example processes in a computer network). If the
messages are not delivered in the order they were sent (for example
when the communica- tion delay time is arbitrary) then two players
require at least *n* - 1 messages. In an
asynchronous network, where the messages are delivered in the order
they were sent, 0.88*n* messages suffice. In a synchronous
0.586*n* messages suffice and 0.536*n* messages are
required in the worst case. We exhibit a simple randomized
algorithm with expected worst-case cost of 0.5*n* messages,
and a deterministic algorithm for *k* __>__ 2
players with a cost well below *n* for all *
k* = o(sqrt *n*). The graph-theoretic
framework we formulated for expressing and analyzing algorithms for
this problem may be of independent interest.

(From a SODA '98 paper by Buhrman et al.)