Mobile Agents on Dynamic Graphs

摘要

At the core of distributed computing there is the necessity to coordinate a group of entities in face of the uncertainty present in the environment. Classically, such uncertainty was mainly the one introduced by the loss or the delay of messages (asynchrony and failures). In this chapter we focus on the uncertainty introduced by the dynamism of the communication topology. We use the paradigm of mobile agents. In such paradigm the computational entities are intelligent messages circulating on top of a dynamic graph. We consider the problems of Exploration, Gathering and Deployment. We survey the most recent results in this interesting and relatively new field.