Brief Announcement: Optimal Deterministic Rendezvous in Labeled Lines

Summary

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 problem was recently considered by Miller and Pelc [17, DISC 2023]. With ℓmax the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous of the agents 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(D2(log* ℓmax)3) 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.