text: The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Omega(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most n. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number L of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log L + loglog n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most L leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Omega(log L + loglog n)$ bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.
  @cite_6: If two searchers are searching for a stationary target and wish to minimize the expected time until both searchers and the lost target are reunited, there is a trade off between searching for the target and checking back to see if the other searcher has already found the target. This note solves a non-linear optimization problem to find the optimal search strategy for this problem.
  @cite_24: 
  @cite_2: Suppose that @math players are placed randomly on the real line at consecutive integers, and faced in random directions. Each player has maximum speed one, cannot see the others, and doesn't know his relative position. What is the minimum time @math required to ensure that all the players can meet together at a single point, regardless of their initial placement? We prove that @math , @math , and @math is asymptotic to @math We also consider a variant of the problem which requires players who meet to stick together, and find in this case that three players require @math time units to ensure a meeting. This paper is thus a minimax version of the rendezvous search problem, which has hitherto been studied only in terms of minimizing the expected meeting time.
  @cite_10: We consider a collection of robots which are identical (anonymous), have limited visibility of the environment, and no memory of the past (oblivious); furthermore, they are totally asynchronous in their actions, computations, and movements. We show that, even in such a totally asynchronous setting, it is possible for the robots to gather in the same location in finite time, provided they have a compass.
  @cite_12: We consider the problem of a rendezvous (coordinated meeting) of distributed units (intelligent agents in network computing or autonomous robots). The environment is modeled as a graph, the node labeling of which may not be “common knowledge” to the units, due to protocol and naming convention mismatch, machine faults, status change, or even hostility of the environment. Meeting of such units is likely to be a basic procedure in the area of distributed “intelligent agent” computing and in the domain of coordinated tasks of autonomous robots. The crux of the problem which we present here and initiate research on, is the breaking of potential symmetry while the units dynamically move. The units are more intelligent (computing power, control and memory) than simple (traditional) pebbles or tokens, and our algorithms will make use of this capability for speeding up the convergence to a common place (e.g., we will allow units to meet exchange information and depart). We consider both randomized protocols and deterministic (but non-uniform) protocols; the problem is unsolvable by a uniform deterministic algorithm. The deterministic procedure employs ideas from design theory and achieves O(n) time, while the randomized methods are based on random walks and may achieve O(n) time where k is the number of agents.
summary: A natural extension of the rendezvous problem is that of gathering @cite_10 @cite_24 @cite_2 @cite_6 , when more than two agents have to meet in one location. @cite_12 the authors considered rendezvous of many agents with unique labels.