Universal Rendezvous of Anonymous Agents with Footprints

Universal Rendezvous of Anonymous Agents with Footprints Bibhuti Das∗

Abstract

arXiv:2608.08981v1 [cs.DC] 10 Aug 2026

Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem. keywords: anonymous graph, anonymous agent, rendezvous, footprints, universal algorithm

∗

Département d’informatique, Université du Québec en Outaouais, Gatineau, Québec J8X 3X7, Canada. dasbibhuti905@gmail.com

1

Introduction

The task of deterministic rendezvous for two anonymous mobile agents navigating synchronously in an anonymous network, modeled as a connected, unlabeled graph, calls for their meeting at some node, by executing the same deterministic algorithm. The initial nodes of the agents in the network are chosen by an adversary. The agents need to meet at some node in the same round to solve rendezvous. The methodological importance of rendezvous comes from the fact that it is a symmetry-breaking task equivalent to the fundamental distributed task of leader election between the agents (cf., e.g., [21]), which asks for one of the agents to become leader and the other a nonleader. In computer networks, the mobile agents may be software agents navigating in a network to consult a distributed database whose parts are located in nodes of the network. They can also be viewed as the mobile robots navigating in a network of corridors of a contaminated mine to collect samples of the ground or of the air. In both cases, the task of rendezvous may be needed to exchange data collected so far for planning future actions.

1.1

The model and the problem

We consider a network represented by a simple undirected connected graph G = (V, E) that can be either finite or countably infinite. The degrees of all nodes are finite but there is no global known upper bound on node degrees. Nodes are unlabeled, but ports at each individual node of degree d are numbered by integers 0, 1, . . . , d − 1. There is no coherence between port numbers at two extremities of an edge. Two mobile agents start at different nodes of the network, called their bases chosen by an adversary. The agents start simultaneously and navigate synchronously in the network. To achieve rendezvous, they must meet at some node in the network in the same round. 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 an algorithm, possibly valid only for this instance, that guarantees rendezvous for it. A rendezvous algorithm is universal for a class of instances, if it is valid for all feasible instances from this class. In each round, an agent can either stay at the current node or move to an adjacent node by a chosen port. When an agent arrives at a node, it sees its degree and the port number by which it enters the node. Agents are identical (they have no labels) and execute the same deterministic algorithm. They have an unbounded memory; computationally they are modelled as Turing machines. A rendezvous between agents occurs when they are at the same node in the same round. The agents can cross each other in an edge going in opposite directions but they do not notice it. This is a standard assumption for synchronous rendezvous in networks (cf. [9, 13]). In this paper, we consider the model with footprints (cf. [17]), whenever an agent visits an unmarked node, it leaves a permanent mark, called footprint, on it, and all footprints are identical. Let G be any graph and v a node in this graph. A path of length k starting at v is a sequence of integers (p1 , q1 , p2 , q2 , . . . , pk , qk ), such that there exist nodes v = v0 , v1 , ..., vk in the graph G, for which vi is adjacent to vi+1 , where i = 0, 1, . . . k − 1, and edge {vi , vi+1 } has ports pi+1 at its endpoint vi and qi+1 at its endpoint vi+1 . Node vi is called the ith node of π. For a path π = (p1 , q1 , p2 , q2 , . . . , pk , qk ) starting at v0 , the reverse path rev(π) is the path (qk , pk , qk−1 , pk−1 , . . . , q1 , p1 ), starting at vk . The view from v in G, denoted V(v, G), is the tree of all paths in G, starting at node v, where the rooted tree structure is defined by the prefix relation of sequences of integers. This definition is equivalent to that from [22], where the notion of view was introduced. Nodes u and v in G are 2

called symmetric, if V(u, G) = V(v, G). In the model with footprints, Das and Pelc [11] presented universal rendezvous algorithms for four different classes of instances: those with symmetric bases, those with non-symmetric bases, those on trees, and those with a known upper bound on node degrees. In all the cases, the proposed universal algorithms work for graphs that are finite or countably infinite. However, they remain limited to classes of instances with a prior knowledge. Our aim is to design universal rendezvous algorithm for the class of all instances in the model with footprints without any a prior knowledge.

1.2

Our contribution

The main contribution of this work is to provide an affirmative answer to the following open question from [11]. Does there exist a universal rendezvous algorithm for the class of all instances in the model with footprints? Das and Pelc [11] proposed universal rendezvous algorithms in the model with footprints for two complementary classes: the class of instances with symmetric bases and the class of instances with non-symmetric bases. We design a universal rendezvous algorithm for the class of all instances in the model with footprints, where the underlying graph is an arbitrary connected graph, finite or countably infinite, without any a priori knowledge. This proves that there exists a universal algorithm for the class of all instances in the model with footprints.

1.3

Related work

The rendezvous problem has been investigated both in the deterministic scenario [20] and in the randomized scenario [2, 3]. In many papers, the geometric scenario was considered in the context of the rendezvous task, e.g., in [4]. The extension of the rendezvous problem to several agents is usually called gathering, and was studied, e.g., in [19]. The gathering problem for oblivious robots in the plane was studied in [16], and fault-tolerant aspects of this problem were investigated, e.g., in [1, 8]. Rendezvous was studied both assuming that agents are allowed to mark visited nodes, e.g., using tokens [18], and assuming that they always mark visited nodes by leaving footprints [17], similarly as in the present paper. However, in most of the literature on rendezvous, the study considers a model forbidding any marking of nodes. The symmetry between the agents is often broken by assigning different labels to each of them [13]. It is then assumed that each agent knows its own label but not the other agent’s label. In [6], the authors designed the first rendezvous algorithm that works on arbitrary (even countably infinite) graphs for labeled agents that navigate synchronously, without leaving marks. Deterministic rendezvous of anonymous agents in finite anonymous graphs was previously studied in [9, 14]. In the paper [9], the authors proposed a rendezvous algorithm that works for all non-symmetric initial positions in arbitrary finite graphs with a known bound on their size, using memory logarithmic in this bound. In the work [14], the authors studied the gathering problem of anonymous agents and characterized initial positions that allow gathering. The authors of [11, 17] considered rendezvous in the model with footprints. A large volume of works investigated asynchronous rendezvous in the plane [7, 16] and in networks [5, 10, 12, 15]. 3

2

Universal rendezvous with footprints

In this section, we design a universal rendezvous algorithm for the class of all instances in the model with footprints and prove its correctness.

2.1

Preliminaries

In the model with footprints, whenever an agent visits an unmarked node, it leaves a permanent footprint, and all footprints are identical. We will use the following notion from [11]. Consider an instance (G, u, v) and a path π in G. A parallel run [G, u, v, π] is the following procedure. One agent starts at u, and the other agent starts at v. Let (u0 = u, u1 , . . . , uk ) and (v0 = v, v1 , . . . , vk ) be the sequences of nodes corresponding to path π starting at nodes u and v, respectively. Each agent follows path π in rounds 1, 2, . . . , k. The footprint status for a parallel run [G, u, v, π] of a node ui (respectively vi ) is 1, if this node is marked at its first visit by the agent starting at u (respectively starting at v) during the forward exploration of the path, and it is 0 otherwise. The following proposition from [11] gives a necessary condition on the feasibility of an instance in the model with footprints. Proposition 2.1 If the instance (G, u, v) is feasible then • nodes u and v are non-symmetric, or • nodes u and v are symmetric and there exists a path π of length k in G, such that, for the parallel run [G, u, v, π], there exists an 1 ≤ i ≤ k, for which the footprint status of nodes ui and vi is different. Intuitively, the above condition says that either the views from the agents’ bases are different, or they are equal, but the “input on the ground” (i.e., the footprint status) perceived by the agents along some path must differ. Next, we recall the transformation of binary strings defined in [6]. Consider a binary string L = (l1 l2 . . . ls ) with l1 = 1. Following [6, 11], we define the following transformations of L. First, we construct the binary string T1 (L) from L as follows. Each bit 1 is replaced by 10, and each bit 0 is replaced by 01. Additionally, bits 11 are added at the end. The obtained string T1 (L) has length 2s + 2 and has the following property. Property 1. If we start with two different strings L1 ̸= L2 then none of the transformed strings T1 (L1 ) and T1 (L2 ) can be a prefix of the other (cf. [11]). Next, we construct the string T2 (L) of length 4s + 4 from T1 (L) by replacing each bit 1 by 10 and each bit 0 by 01. Notice that since two strings L1 and L2 may have different lengths, the same is true for the transformed strings T2 (L1 ) and T2 (L2 ). However, they have the following property. Property 2. If L1 ̸= L2 , then there exists an index j, such that the j th bit of T2 (L1 ) is 1 and the j th bit of T2 (L2 ) is 0 (cf. [11]). (Hence, not only T2 (L1 ) and T2 (L2 ) differ in some bit, but it is guaranteed that in some position the bits are 1 and 0, and in some other position the bits are 0 and 1). Finally, we construct T3 (L) from T2 (L) by adding the prefix 011 to it. The transformed string T3 (L) of length 4s + 7 preserves the property of being prefix-free and guarantees that if L1 ̸= L2 then in some position the bits are 1 and 0 and in some other position the bits are 0 and 1. The transformed string T3 (L) has the following additional property. 4

Property 3. The segment corresponding to bits with indices 2,3,4 in T3 (L) is the only segment of three consecutive bits 1 in T3 (L) (cf. [11]). For example, consider L = 10. We have T1 (L) = 100111, T2 (L) = 100101101010, and T3 (L) = 011100101101010.

2.2

High-level idea of the algorithm

The high-level idea of AlgorithmF ootprint, which guarantees rendezvous in any connected graph in the model with footprints, is as follows. From Proposition 2.1, it follows that a feasible instance can have either non-symmetric bases or symmetric bases. If the views from the bases are different, there exists some path that differs when starting from each of the bases. This path, converted to a binary string and transformed, is used to break the symmetry in the agents’ actions, enabling rendezvous. On the other hand, if the views from the bases are the same, then the footprint status perceived by the agents following some path must be different. In other words, by following some path, one agent visits an unmarked node, while the other agent visits the corresponding node by following the same path that is already marked. Based on the footprint status, the agents break symmetry between their actions to meet. Since the agents don’t know when such a difference will be found, the algorithm proceeds by increasing levels. At each level k, an agent explores all paths of length k, and constructs the temporary label Bk (based on port numbers), and the footprint label Fk (based on footprint status). At each level k ≥ 1, the agents first process the bits of the temporary label Bk . If there is no rendezvous at the end of processing all bits of Bk , then the agent processes the bits of the footprint label Fk . In other words, at each level, the agents check the possibility of non-symmetric bases at first, and then check the possibility of symmetric bases. If there is still no rendezvous, the agent then proceeds to the next level. The agents process a bit by being active when the bit is 1 and passive when the bit is 0. An active agent traverses some path and returns to the base, while a passive agent waits at the base. At some point, the path that exhibits the difference (based on port numbers or footprint status) is found and is sufficiently long to reach the base of the passive agent. This causes the agents to process different bits, 1 and 0, synchronously, where the path traversed by one agent forces it to meet the agent that processes bit 0, who is waiting at its base.

2.3

Detailed description of the algorithm

For any k ≥ 1, we define the temporary label Bk of an agent A at level k as follows. Consider all k-length paths starting at the base of A. Each such path is a sequence of length 2k of non-negative integers that are port numbers. Assume that π1k , π2k , . . . , πtk is the list of all paths of length k starting at the base of A, in lexicographically increasing order. Let π1k = (p1 , q1 , p2 , q2 , . . . , pk , qk ). Let bk1 be the concatenation of binary representations of integers p1 , q1 , p2 , q2 , . . . , pk , qk . Similarly, we define bki , for all i = 1, 2, . . . , t. For 1 ≤ i ≤ t, let cki = T3 (bki ). Finally, define the temporary label Bk = ck1 ck1 . . . ck1 ck2 ck2 . . . ck2 . . . ckt ckt . . . ckt | {z } | {z } | {z } t times

t times

5

t times

Next, for any k ≥ 1, we define the footprint label Fk of an agent A at level k. For any k ≥ 1 and 1 ≤ i ≤ t, let vik denote the k th node of πik . Define Vk = s1 s2 . . . st where for 1 ≤ i ≤ t, ( 1 if vik is a marked node at the first visit following path πik by the agent si = 0 if vik is an unmarked node at the first visit following path πik by the agent By the first visit, we mean the visit during the forward exploration of the path πik by the agent. Notice that Vk is a binary string whose first bit can be 0. For each k ≥ 1, let Wk = V1 V2 . . . Vk and fk = T2 (Wk ). Finally, define the footprint label Fk = fk fk . . . fk | {z } t times

The tape of an agent A is defined as the infinite binary string tape(A) as the concatenation of temporary labels Bk , and footprint labels Fk for all k ≥ 1 in the following way tape(A) = (B1 F1 B2 F2 . . . Bk Fk . . .). The position of a bit in the tape is called its index. For each k ≥ 1, the k th block of tape(A) consists of Bk and Fk . Let nk denote the number of k-length paths starting at the base of agent A. For each k ≥ 1, Bk is divided into nk segments. For 1 ≤ j ≤ nk , the j th segment of Bk consists of nk copies of ckj . For 1 ≤ p ≤ nk , the pth copy of ckj in the j th segment of Bk will be related to the traversal of the path πpk by agent A, i.e., the pth path of length k in lexicographic order. On the other hand, for each k ≥ 1, Fk consists of only one segment that has nk copies of fk . For 1 ≤ p ≤ nk , the pth copy of fk in Fk will be related to the traversal of the path πpk by agent A, i.e., the pth path of length k in lexicographic order. The algorithm is executed by an agent A with tape tape(A), starting at its base bA . We assign rapidly increasing time periods to process consecutive bits li of tape(A). During the execution of the algorithm, agent A constructs tape(A) step by step. By the string transformation, for each k, the first two bits of a temporary label Bk are 01. By processing the first bit 1, agent A traverses the lexicographically smallest path of length k and constructs ck1 . As the algorithm proceeds, agent A explores the pth lexicographically ordered path of length k by processing the bits of the pth copy of ck1 . Once agent A explores all paths of length k, it can construct the temporary label Bk and footprint label Fk of tape(A). The period reserved for processing bit li lasts 3i3 rounds. The processing bit li can be in the the th p copy of ckj in the j th segment of Bk , or in the the pth copy of fk in Fk , where k ≥ 1, 1 ≤ j ≤ nk , and 1 ≤ p ≤ nk . Then the processing of bit li concerns the path πpk starting at bA , in the following way: • li = 1. For each 1 ≤ q ≤ k, the agent goes to the q th node of the path πpk , waits for 3i2 − 2q rounds, and returns to the base. Next, the agent waits for 3i3 − k · 3i2 rounds at the base. • li = 0. The agent waits for 3i3 rounds at the base. Note that the agent A starts and ends processing each bit of tape(A) at its base bA . The algorithm is interrupted as soon as the agents meet. The pseudocode of the algorithm, executed by agent A, is presented on the next page.

6

Algorithm 1: AlgorithmF ootprint Initialize i = 1, and B0 = ε; // ε is the empty string for k = 1, 2 . . . do 3 tape(A) = B1 F1 B2 F2 . . . Bk−1 Fk−1 01 and x = |tape(A)|; 4 while i ≤ x do 5 Let li be a bit in the pth copy of ckj in the j th segment of Bk or li be a bit in the pth copy of fk in Fk ; 6 if li = 1 then 7 for q = 1 to k do 8 Go to the q th node of the path πpk , wait for 3i2 − 2q rounds, and return to the base 9 end 10 Wait for 3i3 − k · 3i2 rounds at the base; 11 else 12 Wait for 3i3 rounds at the base; 13 end 14 if j = 1, p = 1, and li is the first bit 1 in Bk and π1k is not the lexicographically largest path of length k then 15 tape(A) = B1 F1 B2 F2 . . . Bk−1 Fk−1 ck1 ck1 and x = |tape(A)|; 16 if j = 1, p = 1, and li is the first bit 1 in Bk and π1k is the lexicographically largest path of length k then 17 tape(A) = B1 F1 B2 F2 . . . Bk−1 Fk−1 Bk Fk and x = |tape(A)|; 18 if j = 1, p > 1, and πpk is not the lexicographically largest path of length k and li is the first bit 1 in the pth copy of ck1 then 19 tape(A) = tape(A).ck1 and x = |tape(A)|; 20 if j = 1, p > 1, and πpk is the lexicographically largest path of length k and li is the first bit 1 in the pth copy of ck1 then 21 tape(A) = B1 F1 B2 F2 . . . Bk−1 Fk−1 Bk Fk and x = |tape(A)|; 22 end 23 i = i + 1; 24 end 25 end 1 2

2.4

Correctness

In this section, we prove the correctness of AlgorithmF ootprint. From Proposition 2.1, it follows that a feasible instance can have either non-symmetric bases or symmetric bases. First, consider the case when the agents start from non-symmetric bases bA and bB . They must have different paths from some length on. Let k be the smallest integer for which there are different paths of length k starting from bA and bB . For an instance of the rendezvous problem, where agents A and B start at bases bA and bB , respectively, where D is the distance between their bases, we define the critical path for A as follows. First, consider the case when k ≤ D. Let π denote the lexicographically smallest among shortest paths from bA to bB . In this case, we call π the critical path of agent A. The length of this path is D. Next, consider the case when k > D. Let π denote the lexicographically smallest k-length path starting at bA , and passing through bB . In this case, we call π the critical path of agent A. The length of this path is k. Next, consider the case when the agents start from symmetric bases bA and bB . Since V(bA , G) = V(bB , G), by Proposition 2.1 there exists a level y ≥ 1 such that the footprint label Fy is different for agent A and for agent B. By the definition of footprint label, for all k ≥ y, Fk is different for agent A and for agent B. Let π denote the lexicographically smallest k-length path starting at bA ,

7

and passing through bB such that k ≥ y. We call π the critical path of agent A. Let us assume that the critical path π of length α of agent A is the j th lexicographically smallest α-length path starting at bA , i.e., πjα = π. The segment of tape(A) corresponding to the j th copy of cαj in the j th segment of Bk or the j th copy of fk in Fk is called the critical segment of agent A. The agents start simultaneously from their bases. However, the agents may start executing their respective critical segments in different rounds based on their views. Remark 2.1 To show that the formulation of the algorithm is correct, we need to prove that if li is the ith bit of tape(A) located in Bk or Fk , then ∀1 ≤ j ≤ k, 3i2 ≥ 2j. Indeed, we have 3i2 ≥ 2i ≥ 2k ≥ 2j, for all 1 ≤ j ≤ k. The following lemma proves the correctness of AlgorithmF ootprint when the agents start from non-symmetric bases bA and bB . Lemma 2.1 Suppose that the agents start executing AlgorithmF ootprint simultaneously, and their bases are non-symmetric. Then the agents meet by the end of the execution of the critical segment by the agent that starts executing its critical segment earlier. Proof: Let A be the agent that starts the execution of its critical segment earlier, and let B be the other agent. If agents start executing their critical segments simultaneously, then the choice of A is arbitrary. Let r1 be the round in which A starts executing its critical segment. Let m − 1 be the index of the first bit in this segment. Hence, agent A starts the execution of the second bit of its critical segment (which is bit 1) in round r2 = r1 + 3 · (m − 1)3 + 1. Since the agents start simultaneously, and the time required for processing the ith bit of their respective tapes is equal to 3i3 rounds for both the agents, agent B also starts processing the mth bit of tape(B) in round r2 . Consider the time interval [r2 , r2 + (D − 1) · 3m2 + D]. During this time interval, agent A traverses its critical path π (of length α), and reaches the Dth node on π by processing the mth bit of tape(A). If the mth bit of tape(B) is 0, then agent A meets agent B at the base bB during the execution of the mth bit of tape(B) by B, because agent B will be waiting at bB , while agent A reaches bB . Otherwise, the mth bit of tape(B) is 1, and we have the following three subcases. 1. the mth bit of agent B is not the first bit 1 of some pth copy of ckj in the j th segment of Bk . Then by the definition of ckj , at least one among the (m + 1)th and (m + 2)th bits of tape(B) is 0, because of Property 3 of string transformation. Since the mth , the (m + 1)th and the (m + 2)th bits of tape(A) are 1, the agents meet at the base bB of B during the execution of the first bit 0 of tape(B) following the mth bit of this tape. During the execution of this bit, agent B waits at its base bB and agent A reaches bB . 2. the mth bit of agent B is the first bit 1 of some pth copy of ckj in the j th segment of Bk . In view of Properties 1 and 2 of string transformation, for some index s, the sth bit of tape(A) is 1, the sth bit of tape(B) is 0. Hence, the agents meet at the base bB of B, during the executions of the sth bits of their tapes. Indeed, during the execution of this bit, agent B waits at its base bB and agent A reaches bB . 3. the mth bit of agent B is in some pth copy of fk in Fk . By the definition of fk , at least one among the (m + 1)th and (m + 2)th bits in Fk of tape(B) is 0, because there are no three consecutive bits 1 in fk . During the execution of this bit, agent B waits at its base bB and □ agent A reaches bB . 8

The following lemma proves the correctness of AlgorithmF ootprint when the agents start from symmetric bases bA and bB . Lemma 2.2 Suppose that the agents start executing AlgorithmF ootprint simultaneously, and their bases are symmetric. Then the agents meet by the end of the execution of the critical segment by the agent that starts executing its critical segment earlier. Proof: Due to the symmetry of the bases and the simultaneous start of the agents, the processing of the bits by both agents proceeds simultaneously for all levels k ≥ 1. Let A be the agent that starts the execution of its critical segment earlier, and let B be the other agent. If agents start executing their critical segments simultaneously, then the choice of A is arbitrary. Let the critical segment of agent A correspond to the pth copy of fk in Fk for some k ≥ 1. By the definition of footprint label, in view of Properties 1 and 2 of string transformation, and by Proposition 2.1, for some index j, the j th bit in the critical segment of A is 1, and the j th bit in Fk of tape(B) is 0. Hence, the agents meet at the base bB of B, during the executions of the j th bits of their tapes. Indeed, during the execution of this bit, agent B waits at its base bB and agent A reaches bB . □ Theorem 2.1 AlgorithmF ootprint is a universal rendezvous algorithm for the class of all instances, where the underlying graph is any connected graph, finite or countably infinite, in the model with footprints. Proof: Consider a feasible instance (G, u, v) in the model with footprints. Suppose the agents start simultaneously. From Proposition 2.1, it follows that a feasible instance can have either nonsymmetric bases or symmetric bases. If the bases are non-symmetric, then rendezvous is guaranteed by Lemma 2.1. In case bases are symmetric, then rendezvous is guaranteed by Lemma 2.2. This proves the theorem. □ The following corollary implied by Theorem 2.1 is the main result of this paper that answers the open question from the paper [11]. Corollary 2.1 There exists a universal rendezvous algorithm for the class of all instances, where the underlying graph is any connected graph, finite or countably infinite, in the model with footprints.

3

Conclusion

In the model with footprints, we proposed a universal rendezvous algorithm for the class of all instances where the underlying graph is any connected graph that is finite or countably infinite. This resolves the open problem of whether a universal rendezvous algorithm exists for the class of all instances in the model with footprints.

References [1] N. Agmon and D. Peleg, Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput. 36 (2006), 56-82. [2] S. Alpern, Rendezvous search on labelled networks, Naval Reaserch Logistics 49 (2002), 256274. 9

[3] S. Alpern and S. Gal, The theory of search games and rendezvous. Int. Series in Operations research and Management Science, Kluwer Academic Publisher, 2002. [4] E. Anderson and S. Fekete, Asymmetric rendezvous on the plane, Proc. 14th Annual ACM Symp. on Computational Geometry (1998), 365-373. [5] 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. [6] S. Bhagat, A. Pelc, How to meet at a node of any connected graph, Proc. 36th International Symposium on Distributed Computing (DISC 2022), 11:1 - 11:16. [7] M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Distributed Computing by Mobile Robots: Gathering, SIAM J. Comput. 41 (2012), 829-879. [8] R. Cohen and D. Peleg, Convergence of autonomous mobile robots with inaccurate sensors and movements, SIAM J. Comput. 38 (2008), 276-302. [9] J. Czyzowicz, A. Kosowski, A. Pelc, How to meet when you forget: Log-space rendezvous in arbitrary graphs, Distributed Computing 25 (2012), 165-178. [10] J. Czyzowicz, A. Labourel, A. Pelc, How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms 8 (2012), 37:1-37:14. [11] B. Das and A. Pelc, Universal Deterministic Symmetry Breaking Between Anonymous Agents in Networks: Pro. 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2026), 503-523. [12] G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro, Asynchronous deterministic rendezvous in graphs, Theoretical Computer Science 355 (2006), 315-326. [13] A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc. Deterministic rendezvous in graphs. Algorithmica 46 (2006), 69-96. [14] Y. Dieudonné, A. Pelc, Anonymous meeting in networks, Algorithmica 74 (2016), 908-946 . [15] Y. Dieudonné, A. Pelc, V. Villain, How to meet asynchronously at polynomial cost, SIAM Journal on Computing 44 (2015), 844-867. [16] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of asynchronous oblivious robots with limited visibility, Theor. Comput. Sci. 337 (2005), 147-168. [17] Y. Gao, A. Pelc, Sniffing helps to meet: Deterministic rendezvous of anonymous agents in the grid, Theoretical Computer Science 1050 (2025), 115395. [18] 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), IEEE, 592-599. [19] W. Lim and S. Alpern, Minimax rendezvous on the line, SIAM J. on Control and Optimization 34 (1996), 1650-1665. 10

[20] A. Pelc, Deterministic Rendezvous Algorithms, in: Distributed Computing by Mobile Entities, P. Flocchini, G. Prencipe, N. Santoro, Eds., Springer 2019, LNCS 11340. [21] A. Pelc, R.N. Yadav, Using time to break symmetry: universal deterministic anonymous rendezvous, Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), 85-92. [22] M. Yamashita and T. Kameda, Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases, IEEE Trans. Parallel Distrib. Syst. 7 (1996), 69-89.

11

Related documents

• The Self-Evidencing Agent#73948
• The Very Secret Agent#45748
• The Secret Agent#822979
• Host Identity Protocol (HIP) Rendezvous Extension#254561
• Rendezvous of Mobile Deterministic Automata in Graphs#440346