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)
First page number:
Last page number:
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.
Mobile agents; Self-stabilization; Rendezvous; Gathering
Datta, A. K.,
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