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

Find It

UNLV article access

Share

COinS