The Mobile Agent Rendezvous Problem in the Ring - Kranakis, Evangelos

. .

Résumé :
Mobile agent computing is being used in fields as diverse as artificial intelligence, computational economics and robotics. Agents' ability to adapt dynamically and execute asynchronously and autonomously brings potential advantages in terms of fault-tolerance, flexibility and simplicity. This monograph focuses on studying mobile agents as modelled in distributed systems research and in particular within the framework of research performed in the distributed algorithms community. It studies the fundamental question of how to achieve rendezvous, the gathering of two or more agents at the same node of a network. Like leader election, such an operation is a useful subroutine in more general computations that may require the agents to synchronize, share information, divide up chores, etc. The work provides an introduction to the algorithmic issues raised by the rendezvous problem in the distributed computing setting. For the most part our investigation concentrates on the simplest case oftwo agents attempting to rendezvous on a ring network. Other situations including multiple agents, faulty nodes and other topologies are also examined. An extensive bibliography provides many pointers to related work not covered in the text. The presentation has a distinctly algorithmic, rigorous, distributed computing flavor and most results should be easily accessible to advanced undergraduate and graduate students in computer science and mathematics departments. Table of Contents: Models for Mobile Agent Computing / Deterministic Rendezvous in a Ring / Multiple Agent Rendezvous in a Ring / Randomized Rendezvous in a Ring / Other Models / Other Topologies...

Biographie:
Evangelos Kranakis received his B.Sc.(in Mathematics) from the University of Athens, Greece, in 1973 and his Ph.D. (in Mathematical Logic) from the University of Minnesota, USA, in 1980. He held academic positions at the Department of Mathematics of Purdue University, Mathematisches Institut of the University of Heidelberg,Germany, Computer Science Department of Yale University, USA, Universiteit van Amsterdam, and Centrum voor Wiskunde en Informatica (CWI) in Amsterdam, The Netherlands. He joined the School of Computer Science, Carleton University, Canada, in the Fall of 1991. He has published in the analysis of algorithms, bioinformatics, communication and data (ad hoc and wireless) networks, computational and combinatorial geometry, distributed computing, and network security. He became Carleton University Chancellor's Professor in 2006. Danny Krizanc received his B.Sc. from University of Toronto, Canada, in 1983 and his Ph.D. from Harvard University, USA, in 1988, both degrees in Computer Science. He held positions at the Centruum voor Wiskunde en Informatica, Amsterdam, The Netherlands, the University of Rochester, Rochester, New York and Carleton University in Ottawa, Canada before joining the Department of Mathematics and Computer Science at Wesleyan University in 1999. His research focus is the design and analysis of algorithms, especially as applied to distributed computing, networking and computational biology. Euripides Markou received his B.Sc. (in Physics) from the University of Ioannina, Greece, in 1993 and his Ph.D. (in Theoretical Computer Science) from the National Technical University of Athens, Greece, in 2003. He has been a postdoctoral research fellow at the Universit? du Qu?bec en Outaouais, and at McMaster University, Canada, at the National and Kapodistrian University of Athens, Greece and at the Laboratoire Bordelais de Recherche en Informatique (LaBRI), France before joining the Department of Computer Science and Biomedical Informatics at the University of Central Greece in 2008. His research interests include the design of algorithms and the study of the computational complexity for problems especially in the areas of distributed computing, algorithmic game theory, computational geometry and bioinformatics....

Sommaire:
Models for Mobile Agent Computing.- Deterministic Rendezvous in a Ring.- Multiple Agent Rendezvous in a Ring.- Randomized Rendezvous in a Ring.- Other Models.- Other Topologies....