In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds and measured from the moment an agent first wakes up. We denote by τ the delay between the two agents' wake up times. If awake in a given round T, an agent at a node v has three options: stay at the node v, take port 0, or take port 1. If it decides to stay, the agent will still be at node v in round T+1. Otherwise, it will be at one of the two neighbors of v on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem. The problem was recently considered by Miller and Pelc [Distributed Computing, 2025]. With 𝓁_{max} the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in o(D log^* 𝓁_{max}) rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up (τ = 0) and are told their initial distance D. Miller and Pelc also gave an algorithm of optimal matching complexity O(D log^* 𝓁_{max}) when the agents know D, but only obtained the higher bound of O(D² (log^* 𝓁_{max})³) when D is unknown to the agents. In this paper, we improve this second complexity to a tight O(D log^* 𝓁_{max}), closing the gap between the best known lower and upper bounds. In fact, our algorithm achieves rendezvous in O(D log^* 𝓁_{min}) rounds, where 𝓁_{min} is the smallest label within distance O(D) of the two starting positions. We obtain this result by having the agents compute sparse subsets of the nodes to gather at (formally, ruling sets over the line), as well as some general observations about the setting of rendezvous on labeled graphs.

While obtaining optimal algorithms for the most important problems in the LOCAL model has been one of the central goals in the area of distributed algorithms since its infancy, tight complexity bounds are elusive for many problems even when considering deterministic complexities on trees. We take a step towards remedying this issue by providing a way to relate the complexity of a problem Π on trees to its truly local complexity, which is the (asymptotically) smallest function f such that Π can be solved in O(f(Δ) + log* n) rounds. More specifically, we develop a transformation that takes an algorithm A for Π with a runtime of O(f(Δ) + log* n) rounds as input and transforms it into an O(f(g(n)) +log* n)-round algorithm A′ on trees, where g is the function that satisfies g(n)f(g(n)) = n. If f is the truly local complexity of Π (i.e., if A is asymptotically optimal), then A′ is an asymptotically optimal algorithm on trees, conditioned on a natural assumption on the nature of the worst-case instances of Π.

In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds. We count time from the first moment that an agent wakes up, and denote by τ the delay in two agents' wake up times. If awake in a given round T, an agent at a node υ has three options: stay at the node υ, take port 0, or take port 1. If it decides to stay, the agent will still be at node υ in round T + 1. Otherwise, it will be at one of the two neighbors of υ on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem.

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems.