New Directions in Moving and Computing

移动实体的分布式计算（Distributed Computing by Mobile Entities，又称移动与计算）是一个理论研究领域，其目的是了解在空间宇宙中移动的计算实体的局限性和能力。该领域的理论研究将分布式计算与计算几何（特别是对于连续空间）、图论和组合学（特别是对于离散空间）等领域相交叉。虽然我们已经做了很多工作来提高我们对这一领域的认识，但这一领域的更大一部分仍未被探索，仍然是未知的。本研究计划的目标是在三个不同的方向上扩展研究领域，这些方向是在不同但相互关联的目标上铰接的。

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.