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.