Rendezvous of Mobile Deterministic Automata in Graphs

Rendezvous of Mobile Deterministic Automata in Graphs Bibhuti Das∗

Andrzej Pelc†

arXiv:2608.06482v1 [cs.DC] 6 Aug 2026

Abstract Two mobile agents, modeled as identical deterministic finite automata (DFA) navigating in synchronous rounds in a graph with unlabeled nodes, have to meet at some node. The wellresearched task of meeting in a graph is known as rendezvous. Agents start at adversarially chosen distinct nodes in possibly different rounds. An instance of the rendezvous problem is the underlying graph, together with the initial nodes u and v of the agents. Such an instance is feasible, if there exists a DFA (possibly working only for this instance), such that its identical copies starting at nodes u and v, with an arbitrary delay, accomplish rendezvous. A DFA is RV-universal for a class of instances, if it guarantees rendezvous of its copies starting at the designated nodes with arbitrary delay, for all feasible instances of this class. Our goal is to investigate the existence of RV-universal DFA. We start by observing that if agents cannot mark nodes in any way then there does not exist a RV-universal DFA even for the class of instances where the underlying graph is a line. Hence we allow the use of identical pebbles to mark the nodes by the agents. We consider stationary pebbles that can be dropped by agents at nodes but cannot be picked up, and movable pebbles that can be dropped by agents and later picked up. We observe that, even in the more powerful scenario of movable pebbles, if agents are equipped with any finite number of pebbles, there is no RV-universal DFA for the class of all instances. Hence we restrict attention to instances where the underlying graph is a tree. Our main contribution are two contrasting results showing that movability of pebbles is a crucial feature. We first prove that for any finite number of stationary pebbles there is no RV-universal DFA for trees, and then we design a RV-universal DFA for trees, where each agent is equipped with a single movable pebble. keywords: anonymous graph, anonymous mobile agent, deterministic finite automaton, pebble, rendezvous

∗

Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7, Canada. dasbibhuti905@gmail.com † Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7, Canada. pelc@uqo.ca. Partially supported by NSERC discovery grant 2024-03767 and by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.

1

Introduction

Two mobile agents, modeled as identical deterministic finite automata (DFA) navigating in synchronous rounds in a graph, have to meet at some node. The task of meeting of agents in a graph is known as rendezvous. It has been extensively researched, including in papers [7] (SPAA 2012), [17] (SPAA 2019) and [8] (SPAA 2026), due to its fundamental symmetry-breaking character. Even if agents have unbounded memory and computational power, if they are identical, meeting is often impossible, e.g., when they start simultaneously in an anonymous oriented ring. Hence, symmetry between the agents is sometimes broken by assuming that they know their initial location in the graph [5], or by assigning them different labels [19]. In applications, mobile agents may be software agents navigating in a network in order to consult a distributed database whose parts are located in nodes of the network. They can also be mobile robots navigating in a network of corridors of a contaminated mine, too dangerous for human access, with the aim of collecting samples of the ground or of the air. In both cases, rendezvous may be needed to exchange data collected so far and plan future actions. Since mobile agents are often small and simple mass-produced devices with limited memory and computational power, the choice of a DFA to model them, and the assumption that they are identical, seem natural. This is why we make this choice and assumption in the present paper. Nodes of the graph are unlabeled, but ports at each node of degree d are labeled by integers 0, 1, . . . , d − 1. Agents start at adversarially chosen distinct nodes in possibly different rounds. In each round, an agent may stay put at the current node or move to an adjacent node by choosing some port. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are initial positions of the agents. Such an instance (G, u, v) is feasible, if there exists a DFA (possibly working only for this instance), such that its identical copies starting at nodes u and v, with an arbitrary delay, accomplish rendezvous. Saying that the agents are identical copies of a DFA we understand that the two agents are modeled by the same DFA. A simple example of a non-feasible instance is a line of odd length with symmetric port labeling, and agents starting at its extremities. No automaton A (in fact even no Turing machine) may permit rendezvous for this instance if both agents modeled by A start simultaneously. In contrast, a line of odd length and non-symmetric port labeling gives a feasible instance, regardless of the initial positions of the agents. Indeed, a sufficiently large automaton could memorize the line and guarantee rendezvous. A DFA is RV-universal for a class of instances, if it guarantees rendezvous of its copies starting at the designated nodes with arbitrary delay, for all feasible instances of this class. Our goal is to investigate the existence of RV-universal DFA. Such a universal automaton for a large and important class of instances permits us to accomplish the desired task of rendezvous, without knowing in which (feasible) instance of the considered class the agents are navigating.

1.1

The model and the problem

We consider finite simple undirected connected graphs G = (V, E). Nodes of the graph are unlabeled, but ports at each node of degree d are labeled by integers 0, 1, . . . , d − 1. There is no coherence between port numbers at two extremities of an edge. Since we are interested in deterministic finite automata navigating in a priori unknown graphs, the automaton must be able to distinguish all port numbers, in order to transit to a state instructing it to take one of the ports. Hence we assume that all node degrees of considered graphs are bounded by some common constant 2

ℓ (otherwise no single DFA could navigate in all such graphs), and refer to finite simple undirected connected graphs of bounded degree simply as graphs. Since a RV-universal DFA is considered for a class of graphs with node degrees bounded by ℓ, in the construction of such an automaton we assume the knowledge of ℓ. Mobile agents are represented as entities whose actions are modeled by the same deterministic finite automaton. Hence agents are undistinguishable. They navigate in synchronous rounds. They start from two distinct adversarially chosen nodes of the graph, called their bases, in the initial state S0 , possibly in different rounds, also chosen by an adversary. In the beginning, each agent is equipped with ρ pebbles, and all pebbles are identical. (Later on, we explain why agents must use pebbles). We consider two scenarios: pebbles can be either stationary or movable. In each round, an agent is at some node of the graph, carries some number a of pebbles and is in some state S. It gets the following input: the current number a ≥ 0 of pebbles it carries, the degree of the current node, the port number by which it entered this node, or −1, if it stayed put in the current round, and a bit indicating if there is a pebble at the current node. The state S causes the agent to produce an output that has two parts: a pebble action that can be drop, pick or leave and a move action that can be either −1 or a non-negative integer. Seeing a given input in state S, the agent transits to some state S ′ . The output instructs the agent what to do in the next round. The pebble action leave means that the agent does not drop or pick up any pebble. The pebble action drop consists of dropping a pebble at the current node and decreasing the number of currently carried pebbles by 1. It can be executed only if a > 0 and there is no pebble at the current node; otherwise this action has the same result as leave. The pebble action pick consists of picking the pebble at the current node and increasing the number of currently carried pebbles by 1. It can be executed only if there is a pebble at the current node, and only in the scenario of movable pebbles; otherwise this action has the same result as leave. The move action −1 means that the agent stays put in the next round, and the move action m ≥ 0 means that the agent takes port m in the next round. If there is no port m at the current node, the agent stays put. The trajectory of the agent is the infinite sequence of above described steps. We now give a formalization of the above intuitive description. Let {0, 1} be the set of two possibilities for the current node z of the agent: 0 indicates that there is no pebble in z (z is empty), and 1 indicates that there is a pebble in z (z is full). Let P ebbleActions = {pick, drop, leave}. Let P = {0, 1, . . . , ρ} and L = {−1, 0, 1, . . . , ℓ}. The actions of the mobile agent are formalized as a deterministic finite Mealy automaton A = (X, Y, Q, δ, λ, S0 ). X = L × L × {0, 1} × P is the input alphabet and Y = P ebbleActions × L × P is the output alphabet. Q is a finite set of states with a special state S0 called initial. δ : Q × X → Q is the state transition function, and λ : Q → Y is the output function. The meaning of the input and output symbols is the following. At each step of its functioning, the agent is at some node z of the graph, in some state S, and carries some number m ∈ P of pebbles. It sees the degree d ∈ L of the current node and the integer i ∈ L which is −1 or the entry port number. It also learns the bit h ∈ {0, 1} indicating if there is a pebble at the current node. The input I = (d, i, h, m) ∈ X gives the automaton information about these facts. Given the state S, the agent outputs the symbol λ(S) ∈ P ebbleActions × L × P with the following meaning. The first term indicates the pebble action performed by the agent in the current step. The second term indicates the port number the agent should take or the instruction to stay put if this term is −1,

3

or if the given port number is not available. The third term indicates how many pebbles the agent carries in the next step. Since pebble actions are linked to the number of carried pebbles, we have the following restrictions on the possible values of the output function λ. Let I = (d, i, h, m) ∈ X, and λ(S) = (α, j, κ), where α ∈ P ebbleActions, d ∈ L and κ ∈ P . • if α = leave then κ = m; • if α = drop and h = 0 then κ = m − 1; • if α = pick, h = 1 and the scenario is that of movable pebbles then κ = m + 1. Given the input symbol I and being in a current state S, the agent makes the changes indicated by the output function (it possibly drops or picks a pebble as indicated, possibly changes the number of carried pebbles as indicated, and makes the indicated move), and transits to state δ(S, I). The agent starts with ρ pebbles in the initial state S0 , and its starting node is empty (hence its initial input symbol is (−1, 0, ρ)).

1.2

Our contribution

We start by observing that if agents cannot mark nodes in any way then there does not exist a RV-universal DFA even for the class of instances where the underlying graph is a line. Hence we allow the use of identical pebbles to mark the nodes by the agents. We consider stationary pebbles that can be dropped by agents at nodes but cannot be picked up, and movable pebbles that can be dropped by agents and later picked up. We observe that, even in the more powerful scenario of movable pebbles, if agents are equipped with any finite number of pebbles, there is no RV-universal DFA for the class of all instances. Hence we restrict attention to instances where the underlying graph is a tree. Our main contribution are two contrasting results showing that movability of pebbles is a crucial feature. We first prove that for any finite number of stationary pebbles there is no RV-universal DFA for trees, and then we design a RV-universal DFA for trees, where each agent is equipped with a single movable pebble. Our negative result holds even for the class of instances whose underlying graph is a line.

1.3

Related work

Rendezvous of mobile agents in graphs is an extensively studied topic in the distributed computing literature. Many scenarios have been adopted, concerning the capabilities and the behavior of the agents. In the case when more than two agents are required to meet, rendezvous is often called gathering. In most of the papers on rendezvous, it is assumed that nodes of the graph do not have distinct identities, and agents cannot mark nodes. However, scenarios departing from these assumptions were also studied. Rendezvous was considered in graphs whose nodes are labeled [5, 15], or when marking nodes by agents using pebbles is allowed [14]. For a survey of randomized rendezvous we refer to the classic book [1]. Deterministic rendezvous in graphs was surveyed in [16]. Most of the literature on rendezvous considered the synchronous scenario, where agents move in rounds [5, 6, 19]. We follow this assumption in the present paper. In many graphs, e.g., in the oriented ring, symmetry between agents must be broken because otherwise rendezvous is impossible. Most often symmetry is broken by assigning different labels 4

to agents [9, 19]. Sometimes an even stronger assumption is used: in [5], the authors considered rendezvous under the assumption that the agents know their location in the graph (then the initial location can serve as a label). If agents are anonymous and cannot mark nodes then rendezvous is possible only for restricted classes of instances [6]. In many papers, agents are modeled as Turing machines and their memory is unbounded. Other studies concern the minimum amount of memory that agents must have in order to accomplish rendezvous [6, 12]. In this case, agents are modeled as state machines and the number of states is a function of the size of graphs in which they operate. Gathering many finite automata with distinct labels on the infinite line was considered in [13]. To the best of our knowledge, rendezvous of anonymous deterministic finite automata on anonymous graphs, that we consider in the present paper, was never studied before. In many papers, asynchronous gathering and rendezvous was studied in the plane [4, 11] and in graphs [2, 3, 10]. In the plane, agents are modeled as moving points, and it is often assumed that they can see the positions of other agents. For asynchronous rendezvous in graphs, the optimization criterion is the cost, i.e., the total number of edge traversals. In [2], the authors designed almost optimal algorithms for asynchronous rendezvous in infinite multidimensional grids, assuming that an agent knows its position in the grid. In [3, 10] this assumption was replaced by a weaker assumption that agents have distinct identities.

2

Preliminary Results

In this section we prove two preliminary negative results concerning the existence of RV-universal DFA. In order to prove our first result we need the auxiliary notion of an infinite oriented line. This is an infinite oriented graph whose all nodes have degree 2, and ports at the extremities of each edge, corresponding to this edge, are 0 and 1. At each node, we say that the direction corresponding to port 1 is right and the direction corresponding to port 0 is left. Consider any DFA starting at a node of an infinite oriented line in state S0 . Let t2 > t1 be the first two rounds when the automaton is in the same state S. Let τ = t2 − t1 . Let vi , for i = 1, 2, be the node at which the automaton is in round ti . There are three cases: v2 = v1 , v2 is right of v1 , and v2 is left of v1 . Since the trajectory of the automaton in each period (t1 + τ j, t1 + 1 + τ j, . . . , t2 − 1 + τ j), for any j > 0, is a shift of its trajectory in the period (t1 , t1 + 1, . . . , t2 − 1), it follows that in the first case the set of all visited nodes is bounded, in the second case it is a half-line infinite in the direction right, and in the third case it is a half-line infinite in the direction left. We will say that the DFA is bounded in the first case, right-oriented in the second case, and left-oriented in the third case. Without marking nodes, a k-state right-oriented DFA can visit at most k nodes left of its base, and a k-state left-oriented DFA can visit at most k nodes right of its base. We also define a finite oriented line of length x. This is a graph with x + 1 nodes, two of which have degree 1, x − 1 nodes have degree 2, and ports at the extremities of each edge joining nodes of degree 2, corresponding to this edge, are 0 and 1. In a finite oriented line, there is one edge with ports 0, 0 at its extremities, corresponding to this edge. One of these extremities has degree 1. It is called the beginning of the finite oriented line. The other node of degree 1 is called the end of the line. Finally, a line is a graph with two nodes of degree 1 and the remaining nodes of degree 2. We are now ready to prove our first negative result.

5

Proposition 2.1 If the agents cannot mark the nodes in any way, then there does not exist a RV-universal DFA, even for the class of instances whose underlying graph is a line. Proof: Consider any k-state DFA A. We will construct a feasible instance whose underlying graph is a line, for which A does not permit to achieve rendezvous. Consider the behavior of an agent modeled by A, on the infinite oriented line. First suppose that A is bounded and that all nodes visited by A on the infinite oriented line are at distance at most b from the base of A. Let L be the finite oriented line of length 4b + 3, let u be the node at distance b + 1 from its beginning, and let v be the node at distance b + 1 from its end. Consider the instance (L, u, v) and agents with bases u and v, modeled by A. The behavior of both these agents in L is identical to their behavior on the infinite oriented line. Thus the agents will be always at distance at least 1, hence they cannot meet. On the other hand, the instance (L, u, v) is feasible because there exists a DFA that visits all nodes of the line L and identifies its end. Thus agents can go to the end of the line and meet there. Thus we can assume that A is left-oriented or right-oriented. Without loss of generality, assume that the second case holds. Consider the behavior of A on the infinite oriented line, starting at node z in state S0 , and let t2 > t1 be the first two rounds when the automaton is in the same state S. Let τ = t2 − t1 . Let vi , for i = 1, 2, be the node at which the automaton is in round ti . Let ∆ > 0 be the distance between v1 and v2 . z is at some distance δ ≤ k from v1 . Let M be the finite oriented line of length 2∆ + 2k + 1. Consider two disjoint copies M ′ and M ′′ of M . Let w1 be the node at distance 2k + 1 from the beginning of M ′ and let u be the node at distance δ from w1 , on the same side left/right as z with respect to v1 . Let w2 be the node at distance 2k + 1 + ∆ from the beginning of M ′′ and let v be the node at distance δ from w2 , on the same side left/right as z with respect to v1 . Let N be the line resulting from joining the beginnings of M ′ and M ′′ by an edge e with both ports 1 at the extremities, corresponding to e. The agent A(u) starts at its base u, and the agent A(v) starts at its base v. Both agents are modeled by A. Agent A(u) starts τ rounds earlier than agent A(v). The behavior of both agents in instance (N, u, v) is the same as in the infinite oriented line, before each agent visits a leaf or traverses e. Each agent visits a leaf before traversing e and they cannot meet before visiting a leaf. By the construction of the instance, each agent visits a leaf for the first time in the same round and in the same state. Call this round t. It follows by induction on round r ≥ t that in any such round r, both agents are in the same state. In round t, the distance between the agents is odd, as the length 2(2∆ + 2k + 1) + 1 of the line N is odd. In any round r > t, the distance between the agents may either remain unchanged, or increase by 2 or decrease by 2, with respect to the previous round. Hence this distance remains odd, in any round r ≥ t, and thus agents can never meet. It remains to observe that the instance (N, u, v) is feasible. Indeed, an automaton with sufficiently many states can record the distance of its base from the closer leaf. These distances are 2k + 1 and 2k + 1 + ∆, respectively. The agent corresponding to the smaller distance can go to its closer leaf, and the agent corresponding to the larger distance can go to its farther leaf, where the agents will meet. □ In view of Proposition 2.1, in order to get RV-universal automata, we need to allow some marking of nodes. In this paper, marking is done by identical pebbles used by the agents. We consider two types of pebbles: stationary pebbles that can be dropped by agents at nodes but cannot be picked up, and movable pebbles that can be dropped by agents and later picked up. Our

6

second negative result says that, even in the more powerful scenario of movable pebbles, there is no RV-universal automaton for the class of all instances. Proposition 2.2 There does not exist a RV-universal DFA for the class of all instances, even if each agent is equipped with an arbitrary finite number of movable pebbles. Proof: Consider any DFA A using a finite number k of movable pebbles. We will construct a feasible instance for which A does not permit to achieve rendezvous. It is proved in [18] that for any finite number of DFA there exists a finite cubic graph G that cannot be collectively explored by these automata, i.e., at least one node of G will not be visited by any of these automata. Since movable pebbles can be simulated by automata, it follows that there exists a finite cubic graph G that cannot be explored by A using finitely many movable pebbles. Consider the n-node graph G and its node u which is the base of an agent modeled by A. Let v be the node of G that cannot be visited by A using k pebbles. Let (G1 , u1 ) and (G2 , u2 ) be disjoint isomorphic copies of G with nodes u1 , u2 corresponding to the base u. Let v1 and v2 be the nodes in each copy, corresponding to the unvisited node v of G. We construct the graph H as follows. Consider the path P of length 2 with extremities v1 and v2 . Add n leaves adjacent to the mid-point of P , creating the augmented path Q. The graph H is defined as the union of graphs G1 , G2 and Q. The DFA A does not permit us to achieve rendezvous in the instance (H, u1 , u2 ) because agents start at nodes u1 and u2 , respectively, and they cannot reach the path P joining the two disjoint copies of G from which they start. It remains to show that the instance (H, u1 , u2 ) is feasible. Indeed, an automaton with sufficient memory can explore and remember the entire graph H. Thus it can identify the only node z of degree n + 2 in the graph H (which is the mid-point of P together with the added leaves). After this identification, each agent goes to z and stops. □ Proposition 2.2 implies that in order to get a RV-universal automaton, we must not only allow pebbles, but also restrict the class of instances for which a RV-universal automaton is sought. Such a natural class are trees, and hence, from now on, we study the existence of RV-universal automata for the class of instances whose underlying graph is a tree.

3

Nonexistence of RV-Universal Automata with Stationary Pebbles in Trees

In this section, we prove that there does not exist any RV-Universal DFA even for the class of all instances whose underlying graph is a finite line, if the agents modeled by the automaton are initially equipped with finitely many stationary pebbles. The high-level idea of the proof is as follows. Given any DFA A with k states, we construct a feasible instance whose underlying graph is a line, and for which A does not guarantee rendezvous. We first consider two copies of a finite oriented line with beginnings b and b′ , respectively. Then we exchange port numbers 0 and 1 at some nodes of degree 2 in each copy, and we call these nodes red. All other nodes of degree 2 will be called green, and the end of each copy will be called blue. Finally we join the blue nodes by an edge, putting port 1 corresponding to this edge at each blue node. The agents start at nodes b and b′ in the same round. Red nodes are chosen so that: • they are situated in different places in each copy, to guarantee that the instance is feasible; 7

• all red nodes in each copy are farther from the beginning of the copy than all pebbles possibly dropped by A in this copy. As we will see, this is done to ensure that (stationary) pebbles cannot help to meet. The red node in each copy closest to b (resp. to b′ ) is called c (resp. c′ ). • the red nodes farthest from the beginning of each copy, called respectively g and g ′ , are at the same distance from b and b′ , respectively, and have the property that the agents always enter these nodes in the same round and in the same state. We will prove that the only place where agents could possibly meet is the part of the line between nodes g and g ′ . However, the distance between these nodes is odd, and we will show that in each round after reaching g and g ′ for the first time, the distance between the agents either remains the same as in the previous round, or increases by 2 or decreases by 2. Hence, when the agents are between g and g ′ , this distance is always odd, and hence rendezvous is impossible. The rest of this section is devoted to showing that A does not guarantee rendezvous in the line constructed as above. The aim of our first lemma is to restrict the pool of automata that could be potentially RVuniversal. The lemma examines the behavior of an automaton on any infinite line, i.e., any infinite graph all of whose nodes are of degree 2. Lemma 3.1 If a DFA visits a node v of an infinite line more than k times then all nodes that it visits are at distance at most µ from v, for some positive integer µ. Proof: Consider a DFA A that visits a node v of an infinite line more than k times. Let t2 > t1 be the first two rounds when the automaton is in the same state S and visits node v. Let τ = t2 − t1 . The trajectory of the automaton in each period (t1 + τ i, t1 + 1 + τ i, . . . , t2 − 1 + τ i), for any i > 0, is identical. Suppose all nodes of this trajectory are at distance at most µ′ from node v. Since the number of nodes visited before round t1 is at most µ′′ , for some positive integer µ′′ , it follows that all nodes visited by A are at distance at most µ = µ′ + µ′′ from v. □ The above lemma permits us to discard all automata that visit some node of an infinite line more than k times. Indeed, agents modeled by such an automaton and starting sufficiently far, e.g., on a finite oriented line, can never meet, as the sets of nodes visited by them are disjoint. Hence, from now on we may assume that, if our given automaton A operates on an infinite line then it visits each node at most k times. For any node v of an infinite line there are two half-lines determined by v. The next lemma shows that we may restrict attention to automata that, when operating on any infinite line, and given any node v of this line, visit only finitely many nodes of one of the two half-lines determined by v. Lemma 3.2 Consider a DFA A that visits a node v of an infinite line at most k times. Then there exists a half-line H determined by v, and an integer β, such that A visits at most β nodes of H. Proof: Consider any node v of an infinite line and suppose that the automaton is in the half-line H ′ after the last visit of v. Let H be the other half-line determined by v. Let β0 be the number of nodes of H visited by A before the first visit of v, and let βi , for 1 ≤ i ≤ k, be the number of nodes of H visited by A between the (i − 1)th and the ith visit of v. Then the number of nodes of H ever visited by A is at most β = max(β0 , . . . , βk ). □

8

For any node v, we will say that the half-line H ′ ̸= H is the free half-line determined by v. We will need the definition of an infinite pseudo-oriented line. This is either an infinite oriented line, or an infinite oriented line, where at one node, called a special node, the port numbers 0 and 1 are reversed. If a pseudo-oriented line is simply an oriented line, each of its nodes is considered special. For a DFA A located at a special node v of a pseudo-oriented line, the free half-line determined by v may be either the half-line for which, at each node u ̸= v, the port 0 leads towards v, or the half-line for which, at each node u ̸= v, the port 1 leads towards v. In the first case we will call A right-sided, and in the second case we will call it left-sided. Without loss of generality we may assume from now on that A is right-sided. Consider the DFA A located at a special node u of an infinite pseudo-oriented line in some round t0 . Suppose that A is in state Si . Let t2 > t1 ≥ t0 be the first two rounds when the automaton is in the same state S ′ . Let a denote the distance between the locations of the automaton on the line in rounds t0 and t1 . Define l(Si ) as the distance between the locations of the automaton on the line in rounds t1 and t2 (cf. Fig. 1). Also, define x = 2 · l(S1 ) · l(S2 ) · · · l(Sk ), where S1 , . . . , Sk are the states of A. c

S

a S′

Si

l(Si )

Figure 1: State transitions and corresponding trajectories starting from state Si . Now we are ready to construct a feasible instance for which the k-state right-sided automaton A does not guarantee rendezvous. This instance is (L, b, b′ ), for some finite line L, whose nodes of degree 1 are b and b′ . The agents start simultaneously from nodes b and b′ , respectively. In what follows, we describe the line L (cf. Fig. 2). First, we construct two copies C and C ′ of a finite oriented line with beginnings b and b′ , respectively. Since our automaton has only finitely many stationary pebbles at its disposal, we may assume that it does not drop any pebble after some round t. Let e and e′ , respectively, denote the farthest nodes from b and b′ in lines C and C ′ , respectively, visited by round t. Let z denote the distance between b (resp. b′ ) and e (resp. e′ ). Next, we color red some nodes of degree 2 of lines C and C ′ . In each red node we exchange the port numbers 0 and 1. The closest red nodes c and c′ to the beginnings b and b′ , in lines C and C ′ , are at distance z + βx from b and b′ , respectively, where β is the bound from Lemma 3.2. The farthest red nodes g and g ′ from the beginnings b and b′ , in lines C and C ′ , are at distance z + 6βx from b and b′ , respectively. We color red three more nodes between nodes c and g (resp. between nodes c′ and g ′ ). Let ci (resp. c′i ), for i = 1, 2, 3, denote the ith of these red nodes from node c (resp. from node c′ ). • The distance between nodes b and c1 (resp. nodes b′ and c′1 ) is z + 2βx. • The distance between nodes b and c2 is z + 3βx. • The distance between nodes b′ and c′2 is z + 4βx. 9

• The distance between nodes b and c3 (resp. nodes b′ and c′3 ) is z + 5βx. We say that the line segment between nodes c and g (resp. between nodes c′ and g ′ ) is the crucial region of C (resp. C ′ ). Finally, we color blue nodes f and f ′ at distance z + 6βx + 1 from nodes b and b′ , respectively. All other nodes of degree 2 of lines C and C ′ are colored green. This completes the construction of finite oriented lines C and C ′ . Finally, to complete the construction of line L, we join blue nodes f and f ′ by an edge, and put port 1 corresponding to this edge at each blue node.

βx

z

βx

b

e

c

c1

b′

e′

c′

c′1

z

βx

2βx

βx

βx

c2

c′2 2βx

βx

βx

c3

g

f

c′3

g′

f′

βx

crucial region Figure 2: Representation of Line L. The next two lemmas consider the behavior of the DFA A on an infinite pseudo-oriented line. Lemma 3.3 Let u be a special node of an infinite pseudo-oriented line. Let A be located at node u in state S. If A is in state S at a node v of the free half-line determined by u, at distance a + c + i · l(S) from u, for some i ≥ 0 and c ≥ 0, then for all j ≥ i + 1, A will be in the same state S at the node w of the free half-line determined by u at distance a + c + j · l(S) from u. Proof: The proof is by induction on j (cf. Fig. 1). Base Case: Let A be in state S in round t′1 at the node v of the free half-line determined by u, at distance a + c + i · l(S) from node u, for some i ≥ 0 and c ≥ 0. Suppose A is in some state S ∗ ̸= S in round t′2 at the node w of the free half-line determined by u, at distance a + c + (i + 1) · l(S) from u. Let A be in some state S ′ in a round t1 , at the node v1 of the free half-line determined by u, at distance a + i · l(S) from u. Also, let A be in state S ′ in a round t2 , such that t′2 > t2 > t1 , at the node v2 of the free half-line determined by u, at distance a + (i + 1)l(S) from u. Consider the sequence of state transitions starting from state S ′ in the time intervals [t1 , t′1 ] and [t2 , t′2 ]. Let t be the smallest round such that A transitions to different states S1 and S2 from some state S3 in rounds t1 + t ≤ t′1 and t2 + t ≤ t′2 , respectively. This is impossible for a DFA. Thus, the statement of the lemma holds for j = i + 1. Inductive Hypothesis: Suppose the statement of the lemma is true for all j, such that i + 1 < j ≤ m − 1, for some positive integer m. Inductive Step: Suppose A is in some state S ∗ ̸= S in some round t3 at the node z of the free half-line determined by u, at distance a + c + m · l(S) from u. By the inductive hypothesis, A is in state S in rounds t5 and t4 , respectively, at nodes z1 and z2 of the free half-line determined by u, that are at distances a + c + (m − 2) · l(S) and a + c + (m − 1) · l(S), respectively, from u. Now, 10

compare the sequence of state transitions starting from state S in the time intervals [t4 , t3 ] and [t5 , t4 ]. Let t be the smallest round such that A transitions to different states S4 and S5 from some state S4 in rounds t4 + t ≤ t3 and t5 + t ≤ t4 , respectively. This is impossible for a DFA. Thus, the statement holds for j = m. □ Lemma 3.4 Let u be a special node of an infinite pseudo-oriented line. Let A be located at node u in state S. If A is in state S at a node v of the free half-line determined by u, at distance βx from u, then A will be in the same state S at the node w of the free half-line determined by u at distance iβx from u, for all i > 1. Proof: We have βx = a + k1 · l(S) + l1 and iβx = a + k2 · l(S) + l2 where k1 , k2 ≥ 0, and 0 ≤ l1 , l2 < l(S). This implies that (i − 1)βx = (k2 − k1 ) · l(S) + (l2 − l1 ). Since βx is a multiple of l(S), the integer (k2 − k1 ) · l(S) + (l2 − l1 ) must be a multiple of l(S). Since 0 ≤ l1 , l2 < l(S), we must have l1 = l2 . From Lemma 3.3, it follows that A will be in the same state S at nodes u and w of the free half-line determined by u at distances βx and iβx from u, respectively. □ We assume that agents A1 and A2 start simultaneously in the state S0 at nodes b and b′ , respectively. The following lemma shows that the agents will visit the beginnings of the crucial regions at nodes c and c′ in the same state and in the same round. Lemma 3.5 If the agents start simultaneously at nodes b and b′ , then they reach nodes c and c′ in the same state and in the same round. Moreover, their inputs in this round are equal. Proof: The proof is by induction on round t. We prove that in round t ≥ 0, before reaching c and c′ respectively, the inputs of the agents are the same, and the agents are in the same state. Note that all nodes of degree 2 in the line segment between nodes b and c (resp. b′ and c′ ) are green nodes. Base Case: Initially, the agents are located at nodes b and b′ . Both nodes b and b′ have degree 1 and are empty. Since the agents start with ρ pebbles in the initial state S0 , we have the same input (1, −1, 0, ρ) and the same state S0 for both agents in round t = 0. Inductive Hypothesis: Suppose that for all rounds t ≤ r − 1, the inputs of the agents are the same, and the agents are in the same state. Inductive Step: By the inductive hypothesis, the agents have the same input I, and they are in the same state (say S ′ ) in round r − 1. First, consider the state to which agents transition in round r − 1. Since the agents are in state S ′ with the same input I, both agents will transition to the state δ(S ′ , I). Next, we consider the agents’ outputs in round r − 1. Since λ(S ′ ) is identical for the agents, they will have the same value of m in round r. Based on the positions of the agents in round r − 1, we have the following cases: 1. agents are at nodes b and b′ : If j = −1, the agents remain at nodes b and b′ in round r − 1. Thus, d = 1, and i = −1 for both agents in round r. If j = 0, the agents visit a degree 2 node entering through port 0 from nodes b and b′ , respectively. Thus, d = 2 and i = 0 for both agents in round r. Thus the part of the input of both agents concerning the port number and the node degree is the same in round r. 2. agents are at some degree 2 nodes. Suppose the agents are at nodes v and v ′ in round r − 1. If j = −1, the agents remain at nodes v and v ′ in round r − 1. Thus, d = 2, and i = −1 11

for both agents in round r. If j = 0, and the agents visit a degree 2 node entering through port 1 from nodes v and v ′ , respectively, in round r, then d = 2 and i = 1 for both agents in round r. If j = 0, and the agents visit nodes b and b′ by taking port 0 from nodes v and v ′ , respectively, they will enter b and b′ through port 0. Thus, d = 1 and i = 0 for both agents in round r. If j = 1, then the agents visit a degree 2 node entering through port 0 from nodes v and v ′ , respectively, in round r. Thus, d = 2 and i = 0 for both agents in round r. Thus the agents always have the same part of the input concerning the port number and the node degree in round r. It remains to show that the part of the input concerning the presence of a pebble is the same for both agents in round r. If j = 0 or j = 1, then the agents visit a node other than their location in round r − 1. If the nodes visited in round r were visited in some round r′ < r − 1, then by the inductive hypothesis, the agents will have the same bit h in round r. If the nodes visited in round r were not visited in any previous rounds, then h = 0 for both agents. Thus the input of both agents is the same in round r. Therefore, in any round t ≥ 0, before reaching c and c′ respectively, the inputs of the agents are the same, and the agents are in the same state. Hence, if the agents start simultaneously at nodes b and b′ , then they will reach nodes c and c′ in the same state and in the same round. In this round they will have the same input. □ The following lemma shows that if the agents enter the crucial region through nodes c and c′ in the same state and in the same round, then they exit the crucial region through nodes g and g ′ , respectively, in the same state and in the same round. Lemma 3.6 If the agents enter crucial regions through nodes c and c′ in the same state and in the same round, then they reach nodes g and g ′ , respectively, in the same state and in the same round. Moreover, the agents have the same input in this round. Proof: Suppose that the agents A1 and A2 enter their crucial regions through nodes c and c′ , respectively, in some state S in round t0 , for the last time before reaching nodes g and g ′ . By the definition of nodes e and e′ on line L, the number m of carried pebbles in the input of agents remains identical for all rounds t ≥ t0 . Also, d = 2 and h = 0 in the inputs at all nodes in the crucial region. Thus, the part of the input of both agents concerning the node degree, the bit h, and the number of carried pebbles is the same in any round t ≥ t0 , in the crucial region. Consider a red node in the crucial region and consider the first visit of this node by an agent. We examine the states of the agents, the entry ports, and the rounds at this visit. 1. Nodes c1 and c′1 : The distance between c and c1 (resp. between c′ and c′1 ) is βx. The agents visit nodes c and c′ in the same round t0 , have the same input, and are in the same state S, by Lemma 3.5. Therefore, the agents will reach nodes c1 and c′1 for the first time in the same state (say state S ′ ), and in the same round (say round t1 > t0 ). Let T1 = t1 − t0 . Since the agents visit nodes c1 and c′1 for the first time, the entry port must be 1. Thus, A1 and A2 have the same input at nodes c1 and c′1 , respectively. 2. Nodes c2 and c′2 : The distance between c1 and c2 is βx, and the distance between c′1 and c′2 is 2βx. From Lemma 3.4, it follows that A1 and A2 reach nodes c2 and c′2 , respectively, in the same state S ′ . Let t2 and t′2 > t2 be the rounds in which A1 and A2 reach nodes c2 and c′2 , respectively, for the first time. Notice that, all nodes visited by agent A1 during the time 12

interval [t1 + 1, t2 − 1], and all nodes visited by agent A2 during the time interval [t′1 + 1, t′2 − 1] are green. Hence we can apply Lemma 3.4, although this lemma assumes that the agent is in a pseudo-oriented line. Let T2 = t2 − t1 and T2′ = t′2 − t1 . Also, let δ = T2′ − T2 . Since the agents visit nodes c2 and c′2 for the first time, the entry port must be 1. Thus, A1 and A2 have the same input at nodes c2 and c′2 , respectively. 3. Nodes c3 and c′3 : The distance between c2 and c3 is 2βx, and the distance between c′2 and c′3 is βx. Lemma 3.4 guarantees that the agents reach nodes c3 and c′3 in the same state S ′ . Let t3 and t′3 be the rounds in which A1 and A2 reach nodes c3 and c′3 , respectively, for the first time. Let T3 = t3 − t2 and T3′ = t′3 − t′2 . We have T3 − T3′ = δ. Since the agents visit nodes c3 and c′3 for the first time, the entry port must be 1. Thus, A1 and A2 have the same input at nodes c3 and c′3 , respectively. 4. Nodes g and g ′ : The distance between c3 and g is βx, and the distnace between c′3 and g ′ is βx. From Lemma 3.4, it follows that the agents reach nodes g and g ′ in the same state S ′ . Let t4 > t3 and t′4 > t′3 be the rounds in which A1 and A2 reach nodes g and g ′ , respectively, for the first time. Let T4 = t4 − t3 and T4′ = t′4 − t′3 . We have T4 = T4′ . Since the agents visit nodes g and g ′ for the first time, the entry port must be 1. Thus, A1 and A2 have the same input at nodes g and g ′ , respectively. Let T (resp. T ′ ) denote the time required to reach node g by A1 (resp. node g ′ by A2 ) for the first time after round t0 . We have T = T1 +T2 +T3 +T4 = T1 +T2 +(T3′ +δ)+T4 = T1 +(T2 +δ)+T3′ +T4 = T1 + T2′ + T3′ + T4 = T1 + T2′ + T3′ + T4′ = T ′ . Thus, A1 and A2 reach nodes g and g ′ for the first time in the same round t4 = t′4 . In this round, they have the same input and are in the same state S ′ . □ The next lemma shows that if agents A1 and A2 are at nodes g and g ′ , respectively, in the same state and in the same round, then in all successive rounds the distances of agents A1 and A2 from nodes f and f ′ , respectively, are equal. Let r denote the round in which agents visit nodes g and g ′ for the first time. For all t ≥ r, let Dt (resp. Dt′ ) represent the distance between node f (resp. node f ′ ) and the location of A1 (resp. A2 ) in round t. Lemma 3.7 For all rounds t ≥ r, Dt = Dt′ . Proof: We prove the following invariant by induction on round t ≥ r. • in round t, the inputs of the agents are the same and the agents are in the same state. • Dt = Dt′ Base Case: In round t = r, the agents are located at nodes g and g ′ . From Lemma 3.6, it follows that the agents have the same input, and they are in the same state in round r. We have Dr = 1 = Dr′ . Inductive Hypothesis: Suppose that the invariant holds for all rounds t, such that t ≥ r and t ≤ s−1. Inductive Step: By the inductive hypothesis, the agents have the same input I, and they are in the ′ same state (say S ′ ) in round s − 1. Moreover, Ds−1 = Ds−1 . Since the agents are in state S ′ with the same input I, both agents will transition to the state δ(S ′ , I). Thus, the agents have the same state in round s.

13

From Lemma 3.2, it follows that the agents never visit nodes c3 and c′3 after round r. By the definition of nodes e and e′ on line L, the number m of carried pebbles in the input of agents remains identical for all rounds t ≥ r. Also, d = 2 and h = 0 in the inputs at all nodes for all rounds t ≥ r. Thus, the part of the input of both agents concerning the node degree, the bit h, and the number of carried pebbles is the same in round s. We examine the entry port i, and the distances Ds and Ds′ in round s. If j = −1, the agents remain in round s at the nodes visited by ′ them in round s − 1. Thus, Ds = Ds−1 = Ds−1 = Ds′ , and i = −1 for both agents in round s. If j ̸= −1, we have the following cases, based on the location of agents A1 and A2 in round s − 1: ′ 1. A1 is at node g and A2 is at node g ′ in round s − 1. We have Ds−1 = Ds−1 = 1 in round s − 1. ′ If j = 0, agents A1 and A2 visit nodes f and f , entering through port 0 from nodes g and g ′ , respectively. Thus, Ds = Ds′ = 0 and i = 0 for both agents in round s. If j = 1, then agents A1 and A2 visit a green node entering through port 1 from nodes g and g ′ , respectively, in round s. Then Ds = Ds′ = 2 and i = 1, for both agents in round s. ′ 2. A1 is at node g ′ and A2 is at node g in round s − 1. We have Ds−1 = Ds−1 = 2 in round ′ s − 1. If j = 0, agents A1 and A2 , visit nodes f and f in round s, entering through port 0 from nodes g ′ and g, respectively. Thus, Ds = Ds′ = 1 and i = 0 for both agents in round s. If j = 1, then agents A1 and A2 visit a green node entering through port 1 from nodes g and g ′ , respectively, in round s. Then Ds = Ds′ = 3 and i = 1, for both agents in round s. ′ 3. A1 is at node f and A2 is at node f ′ in round s − 1. We have Ds−1 = Ds−1 = 0 in round ′ s − 1. If j = 0, agents A1 and A2 visit nodes g and g , entering through port 0 from nodes f and f ′ , respectively. Thus, Ds = Ds′ = 1 and i = 0, for both agents in round s. If j = 1, then agents A1 and A2 visit nodes f ′ and f entering through port 1 from nodes f and f ′ , respectively, in round s. Then Ds = Ds′ = 1 and i = 1, for both agents in round s. ′ 4. A1 is at node f ′ and A2 is at node f in round s − 1. We have Ds−1 = Ds−1 = 1 in round ′ s − 1. If j = 0, agents A1 and A2 visit nodes g and g, entering through port 0 from nodes f ′ and f , respectively. Thus, Ds = Ds′ = 2 and i = 0, for both agents in round s. If j = 1, then agents A1 and A2 visit nodes f and f ′ entering through port 1 from nodes f ′ and f , respectively, in round s. Then Ds = Ds′ = 0 and i = 1, for both agents in round s.

5. A1 and A2 are at some green nodes v1 and v2 , respectively. By our construction of line L, the distance of a green node from nodes f and f ′ is at least 2. The following three cases are possible (cf. Fig. 3). (a) nodes v1 and v2 are at distance 2 from nodes f and f ′ , respectively. In this case, nodes ′ v1 and v2 are adjacent to nodes g and g ′ , respectively. We have Ds−1 = Ds−1 = 2 in round s − 1. If j = 0, the agents visit a green node entering through port 1 from nodes v1 and v2 , respectively, in round s. Thus, Ds = Ds′ = 3 and i = 1, for both agents in round s. If j = 1, then agents A1 and A2 visit nodes g and g ′ entering through port 1 from nodes v1 and v2 , respectively, in round s. Then Ds = Ds′ = 1 and i = 1, for both agents in round s. (b) nodes v1 and v2 are at distance 3 from nodes f and f ′ , respectively. Moreover, nodes v1 ′ and v2 are adjacent to nodes g ′ and g, respectively. We have Ds−1 = Ds−1 = 3 in round s − 1. If j = 0, the agents visit a green node entering through port 1 from nodes v1 and 14

c3

v1 g

f

c3

v2 g

f

c′3

v2 g ′

f′

c′3

v1 g ′

f′

(a)

(b) κ

c3

v1

g

c′3

v2

g′ κ

f

f′ (c)

c3

v2

c′3

v1

κ g f

g′ κ

f′

Figure 3: Illustration of subcases (a), (b) and (c) of case 5 in the proof of Lemma 3.7. v2 , respectively, in round s. Thus, Ds = Ds′ = 4 and i = 1, for both agents in round s. If j = 1, then agents A1 and A2 visit nodes g ′ and g entering through port 1 from nodes v1 and v2 , respectively, in round s. Then Ds = Ds′ = 2 and i = 1, for both agents in round s. (c) nodes v1 and v2 are at distance κ ≥ 3 from nodes f and f ′ , respectively. Moreover, nodes ′ = κ in v1 and v2 are not adjacent to any of the nodes g and g ′ . We have Ds−1 = Ds−1 round s − 1. If j = 0, the agents visit a green node entering through port 1 from nodes v1 and v2 , respectively, in round s. Thus, Ds = Ds′ = κ + 1 and i = 1, for both agents in round s. If j = 1, the agents visit a green node entering through port 0 from nodes v1 and v2 , respectively, in round s. Thus, Ds = Ds′ = κ − 1 and i = 0, for both agents in round s. Thus, the agents have the same input, and they are in the same state in round s. Moreover, Ds = Ds′ . Hence, for all rounds t ≥ r, the invariant is proved by induction. This proves the lemma. □ We are now ready to show that if agents start simultaneously from the ends of line L then they cannot meet. Theorem 3.1 If the agents start simultaneously at nodes b and b′ of line L, they can never meet. Proof: From Lemma 3.6, it follows that the agents must visit nodes g and g ′ for the first time in the same state and in the same round r. The agents cannot possibly meet before round r because they explore disjoint parts of line L until round r. Suppose that the agents meet in some round r′ > r at some node v ∗ . From Lemma 3.7, it follows that Dr′ = Dr′ ′ . Thus, the distance between node v ∗ and node f is equal to the distance between node v ∗ and f ′ . This is a contradiction because nodes f and f ′ are adjacent. This proves the theorem. □ 15

Corollary 3.1 There does not exist any RV-Universal DFA even for the class of all instances whose underlying graph is a finite line, if the automaton modelling the agents is initially equipped with finitely many stationary pebbles. Proof: Consider agents modeled by a DFA A equipped with finitely many stationary pebbles. Consider the instance (L, b, b′ ), where L is the line constructed above for the automaton A (cf. Fig. 2). The agents modeled by A start simultaneously from nodes b and b′ . From Theorem 3.1, it follows that the agents can never meet. It remains to show that the instance (L, b, b′ ) is feasible. If the agents are modeled by an automaton with a sufficient number of states, then they can explore and remember the entire line L. Thus, the agents can identify the difference in the distances from nodes b and b′ to nodes c2 and c′2 , respectively, and hence they can distinguish between nodes b and b′ . Then both agents go to b and stop. □

4

RV-Universal Automata with Movable Pebbles in Trees

In this section we prove that there exists an RV-universal DFA for the class of all instances whose underlying graph is a tree, in the scenario where each of the agents is initially equipped with a single movable pebble. In other words, we prove the existence of a single automaton that guarantees rendezvous for any feasible instance whose underlying graph is a tree, when identical copies of this automaton start with an arbitrary delay, each equipped with a single movable pebble. As usual in the literature on automata navigating in graphs, we will describe the behavior of the agents by designing an algorithm that can be executed by a deterministic finite automaton, rather than formally describing the construction of an automaton by defining its output and state transition functions. Our algorithm is based on the notion of a basic walk starting at a given node w of the tree. This is the following infinite procedure BW(w). The agent starts at node w and takes port 0. In each round, if the agent entered the current node z of degree d by port j, then it exits it taking port (j + 1) mod d. Starting at any node w of an n-node tree, and executing 2(n − 1) steps of BW(w), the agent visits all nodes of the tree, traverses each edge exactly twice, and gets back to node w. We will use the procedure ShiftPebble that will be called during the execution of a basic walk, when the agent is at a pebble. Thus the agent is at some node y and knows which port number p it should take to get to the next node in the basic walk. Procedure ShiftPebble pick; take port p; drop; Throughout this section, G denotes any tree. We will use the following notion. An instance (G, u, v) is called automorphic, if there is a port preserving automorphism of G carrying u on v. More formally, (G, u, v) is automorphic, if there exists a bijection f : G −→ G, such that f (u) = v, nodes x and y are adjacent if and only if nodes f (x) and f (y) are adjacent, and if p (resp. q) is the port number at x (resp. y) corresponding to edge{x, y} then p (resp. q) is the port number corresponding to edge{f (x), f (y)} at f (x) (resp. at f (y)). The main idea of our algorithm is based on the following lemmas. Lemma 4.1 If the instance (G, u, v) is feasible then it is not automorphic. 16

Proof: Consider a feasible instance (G, u, v) and suppose that it is automorphic. Let A be a rendezvous algorithm for (G, u, v) and let f : G −→ G be a port preserving automorphism of G carrying u on v. Consider agents A(u) and A(v) simultaneously starting at bases u and v respectively and executing algorithm A. Then in some round they must enter the same node z. Let r be the first round when this happens. Since agents execute the same algorithm, by induction on round number r′ < r, if agent A(u) is at node x in round r′ then agent A(v) is at node f (x) in round r′ . In round r − 1 they are at distinct nodes y and f (y). In round r they both take the same port a and hence must enter node z by the same port b. This is a contradiction, because it is impossible to enter a node from distinct nodes by the same port. □ Lemma 4.2 Let (G, u, v) be a non-automorphic instance. Consider basic walks BW(u) and BW(v). Then there exists some step i, such that either the nodes visited in step i in these walks have different degrees, or they have the same degree but the port numbers by which the agents enter these nodes in step i are different. Proof: The proof is by contraposition. Assume that the conclusion of the lemma does not hold, i.e., in each step i, the following condition Ci is satisfied: the nodes ui and vi visited in step i by the basic walks BW(u) and BW(v), respectively, have equal degree, and port numbers by which the agents enter these nodes in step i are equal. We define u0 = u and v0 = v. We will prove that the instance (G, u, v) is automorphic, by showing that the function f defined by f (ui ) = vi , for all i ≥ 0, is a port-preserving automorphism of G carrying u on v. We prove the following invariant by induction on i > 0. • the port number by which the agent leaves node ui−1 in the ith step of the basic walk BW(u) is equal to the port number by which the agent leaves node vi−1 in the ith step of the basic walk BW(v); • the set of port numbers at node uj , for any j ≤ i, used by the agent until step i of BW(u) is equal to the set of port numbers at node vj , for any j ≤ i, used by the agent until step i of BW(v). The invariant holds for i = 1 by the fact that a basic walk starts by taking port 0, and by condition C1 . Suppose that the invariant holds for some i > 0. By condition Ci , the agent entered vi in step i of BW(v) by the same port q as it entered ui in step i of BW(u). Since the degrees of ui and vi are the same, call them d, then the agent leaves ui in step i of BW(u) by port (q + 1) mod d, and leaves vi in step i of BW(v) also by port (q + 1) mod d. These port numbers must be equal. Since the exit port numbers from nodes ui and vi in step i of BW(u) and BW(v) are the same, and the entry port numbers to nodes ui+1 and vi+1 in step i + 1 of BW(u) and BW(v) are the same, by condition Ci+1 , the second part of the invariant is satisfied for i + 1. This proves the invariant by induction. Now we are ready to prove that f is a port-preserving automorphism. Suppose that nodes a and b are adjacent and that p is the port number at a and q is the port number at b corresponding to edge {a, b}. Then edge {a, b} is traversed from a to b in some step i of BW(u). By the invariant and by condition Ci , the agent leaves f (a) by port p and enters f (b) by port q in step i of BW(v). Thus nodes f (a) and f (b) are adjacent and corresponding ports are preserved. It remains to show that f is one-to-one. Suppose that a and b are two distinct nodes of the tree. Suppose that b is visited for the first time later than a in BW(u) and suppose this happens in 17

step i of BW(u). Then, in step i of BW(u), the agent takes a port p at some node b′ to reach b. By the invariant and by condition Ci , in step i of BW(v), the agent takes port p at node f (b′ ) to reach f (b). Since port p is used for the first time at b′ in BW(u), and the set of ports at b′ used in BW(u) until step i − 1 is equal to the set of ports at f (b′ ) used in BW(v) until step i − 1, it follows that port p is used for the first time at f (b′ ) in BW(v). Hence f (a) ̸= f (b). The fact that f (u) = v follows from the definition. Thus f is a port-preserving automorphism carrying u on v, and hence the instance (G, u, v) is automorphic. □

4.1

High-level idea of the algorithm

The high-level idea of our algorithm is as follows. Consider any feasible instance (G, u, v). By Lemmas 4.1 and 4.2 we know that there exists some step i, such that either the nodes visited in step i in the walks BW(u) and BW(v) have different degrees, or they have the same degree but the port numbers by which the agents enter these nodes in step i are different. Call the above condition an accident. Hence, if each agent executes the procedure BW(u) (resp. BW(v)) then an accident must happen in some step. Denote by A(u) the agent with base u and by A(v) the agent with base v. At the beginning, each agent drops its pebble at its base. The algorithm proceeds in phases following the steps of the procedure BW. In the jth phase, each agent shifts its pebble to the node visited by this agent in step j of its basic walk. The crucial part of the phase consists in visiting both pebbles by both agents, trying to verify if there is an accident in the current phase. Determining if node degrees are different is straightforward, but special care must be taken to determine if the entry port numbers are different. However, the main difficulty is to ensure that at the visit of the pebble of the other agent in phase j, this pebble it is still at the node visited by the other agent in step j of its basic walk. This is not straightforward, due to possible initial delay between agents and due to the unknown time of the trip to the other pebble. Once an accident is discovered by the agents, they can break symmetry considering the lexicographic order on the couples (d, q), where d is the degree of the node involved in the accident, and q is the entry port number to this node. After breaking symmetry, one agent stays at its pebble and the other completes a basic walk starting from its pebble and meets the idle agent.

4.2

Detailed description of the algorithm

We present our algorithm for the automaton A(u). The algorithm runs in phases. In the preliminary phase, A(u) drops its pebble at its base u, and executes BW(u) without moving the pebble. Note that an automaton cannot remember where its base is located. If A(u) starts to move by following its initial basic walk, it will periodically encounter nodes with a pebble. The agents can start with an arbitrary delay δ. If δ ≥ 2(n − 1), where n is the number of nodes in the tree, then agents will meet by round 2(n − 1) of the earlier agent because the other agent will be still dormant at its base when the earlier agent gets to this base. Hence, we may assume that δ < 2(n − 1). If deg(u) ̸= deg(v), then A(u) identifies the difference at the first visit of a node with a pebble that has different degree than u. In such a case, if the degree of this node is larger than deg(u), then A(u) waits at this node. If the degree of this node is smaller than deg(u), then A(u) continues its initial basic walk until it sees a node of degree deg(u) with a pebble. This way, the agents will meet in the preliminary phase, at the base of larger degree. Otherwise (when deg(u) = deg(v)),

18

A(u) terminates its preliminary phase when it encounters a node with a pebble 2deg(u) + 1 times during the execution of BW(u). If there is no rendezvous in the preliminary phase, then for all j ≥ 1, A(u) starts its phase j at its pebble. In particular, it starts phase 1 at its base u. A(u) performs the following actions in phase j: 1. Suppose uj denotes the current position of the pebble. Note that in phase 1, uj = u. A(u) executes BW(u). A(u) records the outgoing port number from node uj in this walk (say p), and the entering port number to the next node (say node u′j ) reached through port p from node uj . Call this entering port number q. Consider the next node with a pebble in the basic walk BW(u) from which the agent exits by port p. Call this node y. Let z be the node entered from y by taking port p during the execution of BW(u). Suppose r denotes the entering port number to node z in BW(u). If q < r, then A(u) waits at node z forever. If q > r, then A(u) continues BW(u) until reaching a node with a pebble for the (2 · deg(uj ) + 1)th time, and waits there forever. If q = r, then A(u) continues the execution of BW(u) until visiting a node with a pebble for the 2 · (2deg(uj ) + 1)th time. During the execution of BW(u), if A(u) visits a non-leaf node ν between two consecutive visits of a node with a pebble, then A(u) goes to node ν and waits there forever. 2. A(u) shifts its pebble to the next node in BW(u). Note that u′j denotes the new position of the pebble of A(u). A(u) continues executing BW(u). Suppose t1 denotes the round in which A(u) shifts its pebble. Let w be the first visited node with a pebble such that deg(w) ̸= deg(u′j ) after round t1 . If deg(u′j ) < deg(w), then A(u) waits at the node w forever. If deg(u′j ) > deg(w), then A(u) continues BW(u) until reaching a node of degree deg(u′j ) with a pebble, and waits there forever. If a node with a pebble of a degree different than deg(u′j ) is not encountered, then the agent continues execution of basic walk BW(u) until visiting a node with a pebble for the 2 · (2deg(u′j ) + 1)th time after round t1 . Then it terminates phase j and starts phase j + 1. Note that A(u) starts its phase j ≥ 1 at the node visited in step j − 1 of its basic walk BW(u) and ends this phase at the node visited in step j of its basic walk BW(u). The algorithm is interrupted as soon as the agents meet. The pseudocode of the algorithm, executed by an agent A(u) is presented below.

4.3

Proof of correctness

An agent starting at any node w of an n-node tree, and executing 2(n − 1) steps of BW(w), visits all nodes of the tree, traverses each edge exactly twice, and gets back to node w. However, the agent cannot possibly identify a complete traversal of the tree for unknown n. Since an agent is equipped with a pebble, if it drops its pebble, and executes 2(n − 1) steps of BW(w) under the assumption that there are no other pebbles, then it could identify a complete traversal of the tree by counting the number of times it visits a node with a pebble, which is 2deg(w). As another agent is also navigating in the network, and will also drop a pebble at some node v ̸= w, a complete traversal of the tree is identified by deg(w) + deg(v) + 1 visits of a node with a pebble. If a node with a pebble of a degree different than deg(w) is not encountered, i.e., deg(w) = deg(v), then an agent can identify a complete traversal of the tree by counting 2deg(w) + 1 visits of a node with a pebble. The following lemma ensures that at the end of each phase j ≥ 1 by the earlier agent, each agent’s pebble is located at the node visited in step j of its basic walk. 19

Algorithm 1: RendezvousAlgorithm for agent A(u) // ** Preliminary Phase **// Drop a pebble at u and record deg(u); 2 Execute BW(u) until visiting a node v with a pebble of degree different than deg(u) or until visiting a node v with a pebble 2deg(u) + 1 times; 3 if deg(u) < deg(v) then 4 Wait at v forever; 5 if deg(u) > deg(v) then 6 Continue BW(u) until reaching a node of degree deg(u) with a pebble, and wait there forever; 7 end // ** End of Preliminary Phase **// 8 for j = 1, 2, . . . do // ** Phase j **// 9 uj := the current position of the pebble; // ** In Phase 1, uj = u **// 10 Execute BW(u); 11 p := the outgoing port from node uj during the execution of BW(u); 12 u′j := the node entered by taking port p from node uj ; 13 q := the entering port to node u′j ; 14 y := the next node with a pebble in the basic walk BW(u) from which the agent exits by port p; 15 r := the entering port number to node y; 16 if q < r then 17 Wait at node y forever; 18 if q > r then 19 Continue BW(u) until visiting a node with a pebble for (2 · deg(uj ) + 1) times, and wait there forever; 20 end 21 Continue the execution of BW(u) until visiting a node with a pebble for 2 · (2deg(uj ) + 1) times; 22 if there is a single non-leaf node ν between two consecutive visits of a node with a pebble during the execution of BW(u) then 23 go to node ν and wait forever 24 else 25 Execute ShiftPebble; 26 end 27 u′j := the new position of the pebble; 28 t1 := the round in which A(u) shifts its pebble; 29 Continue the execution of BW(u) until visiting a node w with a pebble, of degree different than deg(u′j ) or until visiting a node w with a pebble 2 · (2deg(u′j ) + 1) times; 30 if deg(u′j ) < deg(w) then 31 Wait at the node w forever; 32 if deg(u′j ) > deg(w) then 33 Continue BW(u) until visiting a node of degree deg(u′j ) with a pebble, and wait there forever; 34 end 35 end 1

20

Lemma 4.3 For each j ≥ 1, at the end of phase j of the earlier agent, each agent’s pebble is located at the node visited in step j of its basic walk. Proof: The proof is by induction on j. Without loss of generality, assume that A(u) is the earlier agent. Base Case: Let t1 and t′1 = t1 + δ denote the rounds in which agents A(u) and A(v) start phase j = 1, respectively. At the beginning of phase 1, the pebble of A(u) (resp. the pebble of A(v)) is located at base u (resp. base v). Let t2 (resp. t′2 ) denote the round in which A(u) (resp. A(v)) shifts its pebble to the node visited in step j of its basic walk. Let t3 (resp. t′3 ) denote the round in which A(u) (resp. A(v)) terminates phase 1. We have t′2 = t1 +δ +2·2(n−1)+1 < t1 +3·2(n−1)+1 and t3 = t1 + 2 · 2(n − 1) + 1 + 2 · 2(n − 1) = t1 + 4 · 2(n − 1) + 1 > t′2 . Thus, the statement is true for j = 1. Inductive Hypothesis: Assume that the statement is true for j = k, i.e., at the end of phase k of the earlier agent, each agent’s pebble is located at the node visited in step k of its basic walk. Inductive Step: Let uk (resp. vk ) denote the node visited in step k of the basic walk of A(u) (resp. A(v)). By inductive hypothesis, at the beginning of phase k + 1, uk (resp. vk ) is the location of the pebble of A(u) (resp. A(v)). Let t4 and t′4 = t4 +δ denote the rounds in which agents A(u) and A(v) start phase k+1, respectively. Let t5 (resp. t′5 ) denote the round in which A(u) (resp. A(v)) shifts its pebble to the node visited in step k +1 of its initial basic walk. Let t6 (resp. t′6 ) denote the round in which A(u) (resp. A(v)) terminates phase k+1. We have t′5 = t4 +δ+2·2(n−1)+1 < t4 +3·2(n−1)+1 and t6 = t4 + 2 · 2(n − 1) + 1 + 2 · 2(n − 1) = t4 + 4 · 2(n − 1) + 1 > t′5 . Thus, the statement holds for j = k + 1. □ During the execution of RendezvousAlgorithm, an agent shifts its pebble in each phase j ≥ 1 by following its basic walk. If one of the agents starts the execution of RendezvousAlgorithm with a delay of δ < 2(n − 1), then it will start each phase j ≥ 1 with the same delay δ. Let t denote the round in which agent A(u) shifts its pebble in phase j. When can it be guaranteed that, after round t, A(u) visits a node with the other agent’s pebble after the pebble’s position has been shifted in phase j? The following lemma answers this question. Lemma 4.4 Let t denote the round in which agent A(u) has shifted its pebble in phase j ≥ 1. Then agent A(u) visits a node with the other agent’s pebble after the position of the pebble has been shifted by the other agent in phase j, within 4(n − 1) steps of the basic walk of A(u) in phase j after round t. Proof: Let t1 and t′1 = t1 + δ denote the rounds in which the agents start phase j ≥ 1. First, assume that A(u) is the earlier agent. From Lemma 4.3, it follows that at the beginning of phase j, A(u) and its pebble (resp. A(v) and its pebble) are located at node uj (resp. node vj ). Let A(u) (resp. A(v)) shift its pebble from node uj to node u′j (resp. from node vj to node vj′ ) in round t2 (resp. round t′2 ). We have t2 = t1 + 2 · 2(n − 1) + 1, and t′2 = t2 + δ. Suppose A(u) visits the node vj for the last time within 4(n − 1) steps of BW(u) after round t2 in some round t. We have t > t2 + 2(n − 1) because, starting from round t2 , after 2(n − 1) steps of BW(u), A(u) will return to u′j ̸= vj . Assume that t ≤ t′2 . We have t ≤ t′2 = t2 + δ < t2 + 2(n − 1) which contradicts the inequality t > t2 + 2(n − 1). Thus, t > t′2 . This concludes the proof in the case when A(u) is the earlier agent. Next, assume that A(u) is the later agent. A(v) shifts its token in round t2 , and A(u) shifts its pebble in round t′2 = t2 + δ. Thus, at A(u)’s first visit of the other agent’s pebble after round t′2 in phase j, this pebble has already been shifted in round t2 by the other agent. This first visit occurs within 2(n − 1) steps of the basic walk of A(u) in phase j after round t′2 = t. □ 21

The following lemma concerns the case in which the degrees of the nodes visited in step j of the agents’ respective basic walks differ. Lemma 4.5 If the degrees of the nodes visited by the agents in step j of their respective basic walks differ, then the agents meet by the end of phase j ≥ 1. Proof: Let j be the smallest positive integer such that the degrees of the nodes visited by the agents in step j of their respective basic walks are different. Let t1 and t′1 = t1 + δ denote the rounds in which the agents start phase j. Without loss of generality, assume that A(u) is the earlier agent. Let A(u) (resp. A(v)) shift its pebble from node uj to node u′j (resp. from node vj to node vj′ ) in round t2 (resp. round t′2 ). Also, the nodes where pebbles are located in rounds t2 + 1 and t′2 + 1 are the nodes visited by agents A(u) and A(v) in step j of their respective basic walks. From Lemma 4.4, it follows that within 4(n − 1) steps of BW(u) after round t2 + 1, A(u) will visit the node vj′ . If deg(u′j ) < deg(vj′ ), then A(u) waits at node vj′ forever, and A(v) will return to vj′ where they will meet. If deg(u′j ) > deg(vj′ ), A(u) continues BW(u) until visiting a node with a pebble (deg(u′j ) + deg(vj′ ) + 1) times and waits there forever, while A(v) will reach this node to complete rendezvous. □ The following two lemmas concern the case in which the degrees of the nodes visited in step j of the agents’ respective basic walks are equal. Lemma 4.6 Assume that the degrees of nodes visited by the agents in step j of their respective basic walks are equal. Then, by the end of phase j ≥ 1, the agents compare the entry ports to the nodes they visited in step j of their respective basic walks. Proof: Let t1 and t′1 = t1 + δ denote the rounds in which the agents start phase j ≥ 1. In these rounds, the agents record the entry port numbers to nodes visited by each of them in step j of their basic walks. Without loss of generality, assume that A(u) is the earlier agent. Let uj (resp. vj ) denote the node where the pebble of A(u) (resp. A(v)) is located in round t1 (resp. round t′1 ). Let u′j (resp. vj′ ) denote the node reached from node uj (resp. node vj ) by following the basic walk. Note that u′j and vj′ are the nodes visited in step j of the agents respective basic walks. We have deg(u′j ) = deg(vj′ ). First, consider the round t2 in which agent A(u) checks the entry port to node vj′ . Let T1 = t1 +1+t2 . A(v) will shift its pebble in round T2 = t′1 +1+4·2(n−1). We have T1 ≤ t1 +1+2(n−1) < t′1 + 1 + 4 · 2(n − 1) = T2 . Thus, A(u) correctly compares the entry ports to nodes visited by the agents in step j of their respective basic walks. Next, consider the round t3 in which agent A(v) checks the entry port to node u′j . Let T3 = t′1 + 1 + t3 . A(u) will shift its pebble in round T4 = t1 + 1 + 4 · 2(n − 1). We have T3 = t′1 + 1 + t3 ≤ t′1 + 1 + 2(n − 1) = t1 + δ + 1 + 2(n − 1) < t1 + 1 + 2 · 2(n − 1) = T4 . Thus, A(v) correctly compares the entry ports to nodes visited by the agents in step j of their respective basic walks. □ Lemma 4.7 If the entry ports to the nodes visited by the agents in step j of their respective basic walks are different, then the agents meet by the end of phase j ≥ 1. Proof: Let k be the smallest positive integer such that the entry ports to the nodes visited by the agents in step k of their respective basic walks are different. Let u′j (resp. vj′ ) denote the nodes visited by the agents in step j of their respective basic walks. Let q (resp. r) denote the entry ports of node u′j (resp. node vj′ ) in the agents’ basic walks. From Lemma 4.6, it follows that in 22

phase j, agents compare the entry ports to nodes visited in step j of their respective basic walks. If q < r, then A(u) waits at node vj′ forever, and A(v) will return to vj′ where they will meet. If q > r, A(u) continues BW(u) until visiting a node with a pebble for (deg(u′j ) + deg(vj′ ) + 1) times and waits there forever, while A(v) will reach this node to complete rendezvous. □ We are now ready to prove the main result of this section. Theorem 4.1 If the instance (G, u, v) is feasible, then agents meet within O(n2 ) rounds from the start of the execution of RendezvousAlgorithm by the earlier agent. Proof: During the execution of RendezvousAlgorithm, each agent shifts the pebble it dropped at its base in the preliminary phase. The shift is by one step, following the basic walk in each phase j ≥ 1. In the preliminary phase, each agent executes 2 · 2(n − 1) steps of its basic walk starting from its base. In each phase j ≥ 1, each agent executes 4 · 2(n − 1) steps of its basic walk, starting from the node visited in step j −1 of its basic walk. Since the instance is feasible, it follows from Lemmas 4.1 and 4.2 that there exists some step j such that either the nodes visited in step j of the basic walks of the agents have different degrees, or they have the same degree but the port numbers by which the agents enter these nodes in step j differ. In the preliminary phase, the agents compare the degrees of bases. In each phase j ≥ 1, the agents compare the entry ports to nodes visited by them in step j of their respective basic walks, and they compare the degrees of the nodes visited in step j of their respective basic walks. During the execution of their respective basic walks in phase j, if the agents visit a non-leaf node ν between two consecutive visits of a node with a pebble then they go to node ν and stop. There are two cases. If the entry ports to nodes u′j and vj′ are different then agents meet by the end of phase j, in view of Lemma 4.7. If deg(u′j ) ̸= deg(vj′ ) then agents meet by the end of phase j, in view of Lemma 4.5. In both cases, j ≤ 2(n − 1) because 2(n − 1) is the number of steps of the basic walk guaranteeing the full traversal of the tree. On the other hand, each phase lasts at most 8(n − 1) rounds. Thus, agents meet within O(n2 ) rounds from the start of the execution of RendezvousAlgorithm by the earlier agent. □ Since RendezvousAlgorithm requires remembering only a bounded number of bits, we have the following corollary. Corollary 4.1 There exists an RV-universal DFA for the class of all instances whose underlying graph is a tree, if each of the agents is initially equipped with a single movable pebble.

5

Conclusion

We first observed that, even in the more powerful scenario of movable pebbles, if agents are equipped with any finite number of pebbles, there is no RV-universal DFA for the class of all instances. Hence we restricted attention to instances where the underlying graph is a tree, and proved two contrasting results concerning the existence of RV-universal DFA for trees, depending on whether pebbles are stationary or movable. However, our initial observation concerning the non-existence of RV-universal DFA for the class of all instances, with any number of movable pebbles, uses a counterexample involving quite strange graphs constructed in [18] that cannot be collectively explored by any number of DFA. Thus it is natural to ask if the existence of a universal automaton is refuted only by very strange graphs. 23

More precisely, how large is the class of instances for which there exists a RV-universal DFA using movable pebbles. We proved that this class contains at least all instances whose underlying graph is a tree. It is an open question if this class is significantly larger.

References [1] S. Alpern and S. Gal, The theory of search games and rendezvous. Int. Series in Operations research and Management Science, Kluwer Academic Publisher, 2002. [2] E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, A. Labourel, Almost optimal asynchronous rendezvous in infinite multidimensional grids, Proc. 24th International Symposium on Distributed Computing (DISC 2010), 297-311. [3] S. Bouchard, M. Bournat, Y. Dieudonné, S. Dubois, F. Petit, Asynchronous approach in the plane: a deterministic polynomial algorithm, Distributed Computing 32 (2019), 317-337. [4] M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Distributed computing by mobile robots: Gathering, SIAM J. Comput. 41 (2012), 829-879. [5] A. Collins, J. Czyzowicz, L. Gasieniec, A. Kosowski, R. A. Martin, Synchronous rendezvous for location-aware agents. Proc. 25th International Symposium on Distributed Computing (DISC 2011), 447-459. [6] J. Czyzowicz, A. Kosowski, A. Pelc, How to meet when you forget: Log-space rendezvous in arbitrary graphs, Distributed Computing 25 (2012), 165-178. [7] Time vs. space trade-offs for rendezvous in trees, Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012), 1-10. [8] B. Das, A. Pelc, Universal Deterministic Symmetry Breaking Between Anonymous Agents in Networks, Proc. 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2026), 503-523. [9] A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc. Deterministic rendezvous in graphs. Algorithmica 46 (2006), 69-96. [10] Y. Dieudonné, A. Pelc, V. Villain, How to meet asynchronously at polynomial cost, SIAM Journal on Computing 44 (2015), 844-867. [11] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of asynchronous robots with limited visibility, Theoretical Computer Science 337 (2005), 147-168. [12] P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees, ACM Transactions on Algorithms 9 (2013), 17:1-17:24. [13] Y. Gao, A. Pelc, Gathering teams of deterministic finite automata on a line, Proc. 28th Conference on Principles of Distributed Computing (OPODIS 2024), 11:1 - 11:17. [14] E. Kranakis, D. Krizanc, N. Santoro and C. Sawchuk, Mobile agent rendezvous in a ring, Proc. 23rd Int. Conference on Distributed Computing Systems (ICDCS 2003), 592-599. 24

[15] A. Miller, A. Pelc, Fast deterministic rendezvous in labeled lines, Proc. 37th International Symposium on Distributed Computing (DISC 2023), 29:1 - 29:22. [16] A. Pelc, Deterministic rendezvous algorithms, in: Distributed Computing by Mobile Entities, P. Flocchini, G. Prencipe, N. Santoro, Eds., Springer 2019, LNCS 11340. [17] A. Pelc, R. Yadav, Using Time to Break Symmetry: Universal Deterministic Anonymous Rendezvous, Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019) 85-92 [18] H. Rollik, Automaten in planaren Graphen, Acta Informatica 13 (1980) 287–298 (also in Lecture Notes of Computer Science, Vol. 67, 1979, pp. 266–275). [19] A. Ta-Shma and U. Zwick. Deterministic rendezvous, treasure hunts and strongly universal exploration sequences, ACM Trans. Algorithms 10 (2014), 12:1-12:15.

25

Related documents

• The transition probabilities on wheel graphs: An application of evolutionary games on graphs#298193
• Learning Random Geometric Graphs Drawn in Probabilistic Metric Spaces#467120
• Exponential random graph models with soft clique constraints#622581
• Counterexamples to the Mao-Wu-Xu spectral conjecture and a three-scale boundary for spherical random graphs#1013687
• Universal Rendezvous of Anonymous Agents with Footprints#441757