For interest sake this observation has been included to illustrate the generality of the rendezvous search problem. Trying to perform rendezvous search has some very key features that are pervasive in computer science. The problems of task load balancing, especially on multi-processor systems, and process synchronization in parallel BFS seem to share many of the complexity problems that we have to deal with here.
The trade-off between the expected gain from continued search must be balanced against the effort taken to synchronize the global process, to minimize the amount of wasted search when a solution has been found by one of the processes [agents].
The similarity between the rendezvous search and parallel BFS is as follows. Both have the property that the next search region is polynomially larger than the current one. Having finished a level of search the alternatives are to,
The question is, once we have an efficient method of search for the single agents, how do we balance off the relationship between search and co-ordination. The relationship that we want to consider then, is,
the expected gain versus the cost of co-ordination. Why co-ordinate at all? Co-ordination reduces the amount of wasted search after an agent discovers a solution. It is the intention to minimize this waste, in the interest of laziness or rather efficiency.
