Deterministic Rendezvous with Detection Using Beeps

DOI10.1007/978-3-319-28472-9_7zbMATH Open1359.68016arXiv1709.06214OpenAlexW2398465054MaRDI QIDQ5890529FDOQ5890529

Publication date: 10 March 2016

Published in: Algorithms for Sensor Systems, International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps. We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents can always achieve rendezvous with detection as well...

Full work available at URL: https://arxiv.org/abs/1709.06214

Recommendations

zbMATH Keywords

graph algorithms algorithm synchronous deterministic detection rendezvous synchronous network deterministic rendezvous beep

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cites Work

Cited In (3)

This page was built for publication: Deterministic Rendezvous with Detection Using Beeps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890529)