Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

CHALOPIN_2007-RendezVousOfMobileAgents

Jérémie Chalopin, Shantanu Das, Nicola Santoro. Rendezvous of mobile agents in unknown graphs with faulty links. In Distributed Computing, Volume 4731, Pages 108-22, 2007.

Download

Download paper: Follow the link

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

A group of mobile agents wandering among the nodes of a network have to gather together in a single node of the graph; This problem known as the Rendezvous problem has been studied extensively but only for networks that are safe or fault-free. In this paper, we consider the case when some of the edges in the network are dangerous or faulty such that any agent entering one of these nodes would be destroyed. Our objective is to minimize the number of agents that are destroyed and achieve rendezvous of all the surviving agents. We determine under what conditions this is possible and present algorithms for achieving rendezvous in such cases. Our algorithms are for arbitrary networks with an arbitrary number of dangerous channels; thus our model is a generalization of the case where all the dangerous channels lead to single node, called the Black Hole. We do not assume prior knowledge of the network topology; In fact, we show that knowledge of only a “tight †bound on the network size is sufficient for solving the problem.

Contact

Jérémie Chalopin
Shantanu Das
Nicola Santoro

BibTex Reference

@InProceedings{CHALOPIN_2007-RendezVousOfMobileAgents,
   Author = {Chalopin, Jérémie and Das, Shantanu and Santoro, Nicola},
   Title = {Rendezvous of mobile agents in unknown graphs with faulty links},
   BookTitle = {Distributed Computing},
   Volume = {4731},
   Pages = {108--22},
   Publisher = {Springer Berlin / Heidelberg},
   Year = {2007}
}

EndNote Reference [help]

Get EndNote Reference (.ref)