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.