New Directions in Moving and Computing

点击翻译按钮获取中文摘要

Distributed Computing by Mobile Entities, (a.k.a. Moving and Computing), is a theoretical research field whose aim is to understand limitations and abilities of computational entities moving in a spatial universe. The theoretical research in this area intersects distributed computing with the fields of computational geometry (especially for continuous spaces), and graph theory and combinatorics (especially for discrete spaces). While so much has been done to advance our knowledge of this field, the larger part of the territory is still unexplored and remains uncharted. This research program has the goal to expand the research territory in three different directions, articulated over distinct but inter-related goals. The first direction is motivated by the growing and interesting research area of highly dynamic graphs, where topological changes are not occasional or limited events (e.g., caused by faults) but rather continuous and ubiquitous. These ”ever changing” systems are being investigated within distributed computing in traditional settings (i.e. with stationary entities). The goal of this direction of the program is to extend to time-varying graphs the study of computational and complexity issues arising when the computational entities are mobile; i.e., studying ”moving and computing in an ever changing universe”. Another direction is inspired by the investigations in the new inter-disciplinary field referred to as ”programmable matter”. In this field, matter is often envisioned as a very large number of very small computational particles, programmed to collectively perform a task. Of particular interest, from the distributed computing viewpoint, is the fact that, in spite of the very large number and very small size of the particles, their universe is one of entities that compute and move; that is, the framework is still “moving and computing” albeit at a “micro- scale”. The goal of this direction of the research program is to extend to such a scale the study of moving and computing. The third direction is motivated by the fact that, amid the rapid development of the field, there are still deep fundamental gaps in our knowledge, especially in the case of continuous spaces. Of special concern are the existing feasibility gaps; i.e., those about structural properties of the entities or of the environment that can determine whether or not a problem is solvable. The goal of this part of the research program is to fill some of these gaps, so to strengthen the foundations of distributed computing by mobile entities. Clearly all sub-goals require the invention and development of new algorithmic and analytic tools, as well as the refinement and extension of existing ones. Also, the knowledge acquired in these new directions would expand our understanding of the fundamental nature and basic principles of moving and computing.