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.88n messages suffice. In a synchronous 0.586n messages suffice and 0.536n messages are required in the worst case. We exhibit a simple randomized algorithm with expected worst-case cost of 0.5n 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.)