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.