Distributed Computing and Mobility

这个项目关注的是在交互实体是自治和分散的，但也是移动的环境中的计算。这些环境由非常不同的系统组成，包括支持软件移动代理的网络、机器人群和机器人网络、车辆网络、移动传感器网络等。我们认为相同、简单、“一次性”的实体可以廉价地创建，损坏或“丢失”的实体可以很容易地替换。尽管各实体各自“软弱”，但我们希望这些实体能够共同解决复杂的任务。换句话说，计算能力不在于单个实体，而在于“团队”。这个项目专注于在这样的环境中计算的核心非常基本的问题：可计算性和复杂性；也就是说，像这样的问题：什么问题可以解决？在什么情况下？多么?代价是什么？具体地说，目标总是确定什么是最小的假设(例如，实体的能力，对环境的限制)允许解决给定的问题。问题范围从选举领导人(临时协调员)，到创建环境地图；从定位黑洞(破坏传入代理的有害主机)，到净化被移动入侵者(例如，病毒)感染的网络；从聚集分散在地形上的自动移动车辆(例如，坦克)，到在地形上分散移动传感器，以获得对空间的统一覆盖(例如，用于监视)。尽管存在差异，但在所有这些背景下都出现了相同的基本原则。这些原理的发现是一个新的重要的长期研究挑战；对它们的研究是本项目的主要潜在目标。

This project is concerned with computing in environments where the interacting entities are autonomous and decentralized, but also mobile. These environments comprise very different systems, including networks supporting software mobile agents, robotic swarms and robotic networks, vehicular networks, mobile sensors networks, etc. The entities we consider are identical, simple, "disposable", so they can be created inexpensively, and damaged or "lost" ones can be easily replaced. Although individually "weak", we want the entities to be able, collectively, to solve complex tasks. In other words, the computational capabilities lie not in the single entity but within the "team". This project focuses on the very basic issues at the heart of computing in such environments: computability and complexity; that is, on question like: what problems can be solved ? under what conditions ? how? at what cost ? In particular, the aim is always to determine what minimal hypotheses (e.g., capabilities of the entities, restrictions on the environment) allow a given problem to be solved.The problems range from electing a leader (a temporary coordinator), to creating maps of the environment; from locating black holes (harmful hosts that destroys incoming agents), to decontaminating a network being infected by a mobile intruder (e.g. a virus); from gathering autonomous mobile vehicles (e.g., tanks) dispersed on a terrain, to scattering mobile sensors on a terrain so to obtain a uniformly coverage of the space (e.g., for surveillance). In spite of the differences, the same fundamental principles occur in all these contexts. The discovery of these principles is a new important long-term research challenge; their study is the main underlying goal of this project.