Distributed Computing by Mobile Entities

The past two decades have seen the rapid growth and development of the field of distributed computing by mobile entities, whose concern is the study of the compu- tational and complexity issues arising in systems of decentralized computational entities operating in a spatial universe U. The entities can move in U (their movement is constrained by the nature of U), and are autonomous in their actions (e.g., they are not directed by an external controller). Depending on the nature of U, two different settings are usually identified. The first setting, called discrete universe (sometimes, netscape or graph world), is when U is a simple graph and the entities, usually called agents, move from node to neighboring node. This setting has a long history. The pioneering work of Shannon in 1951 on Exploration [6] was the first of a prolific line of algorithmic investigations on computations by a single agent. It was, however, only later that multiple agents (two, to be precise) were first considered [2]. The distributed computing concerns started in full in 2001 with the study of the Black-Hole Search [3, 4] and Intruder Capture [1] problems. Interestingly, in parallel and independently of this theoretical work, the notion and use of mobile agents were being intensively investi- gated in other fields, noticeably AI and software engineering. Indeed, the use of mobile software agents has been very popular in networked environments, ranging from the Internet to the Data Grid, both as a theoretical paradigm and as a system-supported programming platform; in these fields, the theoretical research had focused mainly on the descriptive and semantic concerns. The other setting, called continuous universe, is when U is a Euclidean space that the entities, usually called robots, can perceive and move in. The continuous setting had long been investigated in the traditional fields of AI, robotics, and control. Within the distributed computing community, the setting was introduced in 1996 with the study of the Pattern Formation problem [7, 8]. The investigations in the field were initially sporadic; this situation has drastically changed over the years, and a continuously increasing number of algorithmic investigations examine this setting. A comprehensive snapshot of the status of the research in this setting at that time appeared in 2012 [5]. In both settings, the research concern is on determining what tasks can be performed by the entities, under what conditions, and at what cost. In particular, the central question is to determine what minimal hypotheses allow a given problem to be solved. Encompassing and modeling a large variety of application environments and sys- tems, from robotic swarms to networks of mobile sensors, from software mobile agents in communication networks to crawlers and viruses on the Web, the theoretical research in this area intersects distributed computing with the fields of computational geometry (especially for continuous spaces), control theory, graph theory, and com- binatorics (especially for discrete spaces). In spite of the apparent differences between the two settings, and of the distinct technical tools required in each, at a higher level, the basic principles are similar; the vision and mind frame required to examine questions and solve problems share many commonalities. This fact has allowed ideas, problems, and questions to be transferred from one setting to the other. Indeed, it is quite common for researchers in the field to do research in both settings