Optimal Deterministic Rendezvous in Labeled Lines
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911466324492288 |
|---|---|
| author | Bourreau, Yann Narayanan, Ananth Nolin, Alexandre |
| author_facet | Bourreau, Yann Narayanan, Ananth Nolin, Alexandre |
| contents | In a rendezvous task, some mobile agents dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with $2$ 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 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 $\ell_{\max}$ the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in $o(D \log^* \ell_{\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^* \ell_{\max})$ when the agents know $D$, but only obtained the higher bound of $O(D^2 (\log^* \ell_{\max})^3)$ when $D$ is unknown to the agents.
We improve this complexity to a tight $O(D \log^* \ell_{\max})$. In fact, our algorithm achieves rendezvous in $O(D \log^* \ell_{\min})$ rounds, where $\ell_{\min}$ is the smallest label within distance $O(D)$ of the two starting positions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04564 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Deterministic Rendezvous in Labeled Lines Bourreau, Yann Narayanan, Ananth Nolin, Alexandre Distributed, Parallel, and Cluster Computing Data Structures and Algorithms In a rendezvous task, some mobile agents dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with $2$ 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 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 $\ell_{\max}$ the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in $o(D \log^* \ell_{\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^* \ell_{\max})$ when the agents know $D$, but only obtained the higher bound of $O(D^2 (\log^* \ell_{\max})^3)$ when $D$ is unknown to the agents. We improve this complexity to a tight $O(D \log^* \ell_{\max})$. In fact, our algorithm achieves rendezvous in $O(D \log^* \ell_{\min})$ rounds, where $\ell_{\min}$ is the smallest label within distance $O(D)$ of the two starting positions. |
| title | Optimal Deterministic Rendezvous in Labeled Lines |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04564 |