Title: Mobile Computationa Entities: Time, Silence, Oblivion
Abstract: Within distributed computing, there is a large research area whose focus is on the com- putability and complexity issues arising when the computational entities are mobile; i.e., capable of moving in the space where they operate. This area, informally called moving and computing (M&C), covers a wide spectrum of (apparently) very different spatial “universes”, ranging from discrete finite spaces (e.g., graphs, networks) to continuous spaces (e.g., 1D, 2D, 3D Euclidean spaces), to infinite discretized spaces (e.g., grids, tesselations). Each universe has specific formal models, and specific problems that the computational entities (variously called agents, robots, particles, etc.) must solve; both models and problems are typically mo- tivated by practical applications arising in other fields (e.g., robotics, software engineering, AI, programmable matter).
In spite of the incredible diversity of application-dependent assumptions, the research in M&C has identified and investigated a group of very specific paradigms: look-compute-move cycles, semi-synchronous adversarial schedulers, (rudimentary) stigmergy, obliviousness.
In this talk, I will describe these paradigms, briefly discuss how they are relevant to the modeling and analysis of artificial biological distributed systems, and argue that some are crucial missing pieces in the traditional investigations on distributed algorithms.