book [4]. Most of the results in this domain can be divided into two classes: those considering the geometric scenario (rendezvous in the line, see, e.g., [9, 10, 17], or in the plane, see, e.g., [7, 8]), and those discussing rendezvous in graphs, e.g., [2, 5]. Some of the authors, e.g., [2, 3, 6, 9, 18] consider the probabilistic scenario where inputs and/or rendezvous strategies are random. Randomized rendezvous strategies use random walks in graphs, which were thoroughly investigated and applied also to other problems, such as graph traversing [1], on- line algorithms [13] and estimating volumes of convex bodies [15]. A generalization of the rendezvous problem is that of gathering [16, 18, 19, 20, 23, 27], when more than 2 agents have to meet in one location. If graphs are unlabeled, deterministic rendezvous requires breaking symmetry, which can be accomplished either by allowing marking nodes or by labeling the agents. Deterministic rendezvous with anonymous agents working in unlabeled graphs but equipped with tokens used to mark nodes was considered e.g., in [22]. In [28] the authors studied gathering many agents with unique labels. In [14, 21, 29] deterministic rendezvous in graphs with labeled agents was considered. How- ever, in all the above papers, the synchronous setting was assumed. Asynchronous gathering under geomet- ric scenarios has been studied, e.g., in [11, 16, 24] in different models than ours: agents could not remem- ber past events, but they were assumed to have at least partial visibility of the scene. The first paper to con- sider deterministic asynchronous rendezvous in graphs was [12]. The authors concentrated on complexity of rendezvous in simple graphs, such as the ring and the in- finite line. They also showed feasibility of deterministic asynchronous rendezvous in arbitrary finite connected graphs with known upper bound on the size. Further im- provements of the above results for the infinite line were proposed in [26]. Gathering many robots in a graph, un- der a different asynchronous model and assuming that the whole graph is seen by each robot, has been studied in [19, 20]. A fundamental notion on which our algorithms are based is that of a tunnel . Consider any graph G and two routes R 1 and R 2 starting at nodes v and w , respectively. We say that these routes form a tunnel, if there exists a prefix [ e 1 , e 2 , . . . , e$_{n}$ ] of route R 1 and a prefix [ e$_{n}$, e$_{n}$$_{−}$ 1 , . . . , e 1 ] of route R 2 , for some edges e$_{i}$ in the graph, such that e$_{i}$ = { v$_{i}$, v$_{i}$ +1 } , where v 1 = v and v$_{n}$ +1 = w . Intuitively, the route R 1 has a prefix P ending at w and the route R 2 has a prefix which is the reverse of P , ending at v . By a slight abuse of terminology we will also say that prefixes [ e 1 , e 2 , . . . , e$_{n}$ ] Let G = ( V, E ) be the connected graph in which the rendezvous must be performed. Let S n be the set of sequences of n positive integers. Let P = { ( i, j, s $^{′}$, s$^{′′}$) | i, j ∈ N , i < j and ∃ n s.t. s $^{′}$, s′′ ∈ S n } . There exists a bijection from the set of positive integers onto P , in view of Proposition 2.2. Let ( ϕ 1 , ϕ 2 , . . . ) be a fixed enumeration of P . All agents have to agree on the same enumeration. It is easy to produce a formula computing φ$_{k}$ for any k . This formula is included in the rendezvous algorithm. For a finite path r in G , we denote by r the path with the same edges as in r , but in the reverse order. Remark that r and r form a tunnel. Proposition 2.2. The set of rational numbers and the set of positive rational numbers are countable. The cartesian product of two countable sets is countable. The set of all finite sequences with terms in a countable set is countable. We now recall some basic facts from set theory, that will be used in further considerations. Proof. Consider an embedding of the graph G in the three-dimensional Euclidean space, with nodes of the graph being points of the space and edges being pairwise disjoint line segments joining them. Consider routes R 1 and R 2 starting at nodes v and w , respectively. Let agent a$_{i}$ execute route R$_{i}$ . Let P be the polygonal line joining v with w , corresponding to the prefixes of the routes, given by the tunnel. Let D be its length defined as the sum of lengths of edges in the corresponding prefixes of the routes. (For non-simple paths in the graph, the same edge is counted many times.) Consider any walks f 1 on R 1 and f 2 on R 2 . Let t ′ be the first moment when an agent leaves its starting point and let t ′′ be the moment when an agent gets to the end of P other than its starting point. For any t ∈ [ t $^{′}$, t$^{′′}$], let d 1 ( t ) be the distance of agent a 1 from its starting point v at time t , counted on the route R 1 , and let d 2 ( t ) be the distance of agent a 2 from its target point v at time t , counted on the route R 2 . Let δ ( t ) = d 2 ( t ) − d 1 ( t ). We have δ ( t $^{′}$) = D and δ ( t $^{′′}$) = d ≤ 0. The function δ is thus a continuous function from the interval [ t $^{′}$, t$^{′′}$] onto some interval [ d $^{′}$, D ], where d ′ ≤ d , in view of the continuity of walks f 1 and f 2 . Since 0 belongs to the interval [ d $^{′}$, D ], there must exist a moment t in the interval [ t $^{′}$, t$^{′′}$], for which δ ( t ) = 0. For this point we have f 1 ( t ) = f 2 ( t ), and the rendezvous occurs. Proposition 2.1. If routes R 1 and R 2 form a tunnel, then they guarantee rendezvous. and [ e$_{n}$, e$_{n}$$_{−}$ 1 , . . . , e 1 ] form a tunnel. 3 Rendezvous in the graph scenario 2 Preliminary notions and results