Self-stabilizing Rendezvous of Synchronous Mobile Agents in Graphs
Document Type
Conference Proceeding
Publication Date
1-1-2017
Publication Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher
Springer Verlag
Volume
10616 LNCS
First page number:
18
Last page number:
32
Abstract
We investigate self-stabilizing rendezvous algorithms for two synchronous mobile agents. The rendezvous algorithms make two mobile agents meet at a single node, starting from arbitrary initial locations and arbitrary initial states. We study deterministic algorithms for two synchronous mobile agents with different labels but without using any whiteboard in the graph. First, we show the existence of a self-stabilizing rendezvous algorithm for arbitrary graphs by providing a scheme to transform a non-stabilizing algorithm to a self-stabilizing one. However, the time complexity of the resultant algorithm is not bounded by any function of the graph size and labels. This raises the question whether there exist polynomial-time self-stabilizing rendezvous algorithms. We give partial answers to this question. We give polynomial-time self-stabilizing rendezvous algorithms for trees and rings. © Springer International Publishing AG 2017.
Keywords
Mobile agents; Self-stabilization; Rendezvous; Gathering
Language
english
Repository Citation
Ooshita, F.,
Datta, A. K.,
Masuzawa, T.
(2017).
Self-stabilizing Rendezvous of Synchronous Mobile Agents in Graphs.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10616 LNCS
18-32.
Springer Verlag.
http://dx.doi.org/10.1007/978-3-319-69084-1_2