Computational issues in systems of mobile entities

移动实体系统中的计算问题

• 批准号: 203254-2011
• 负责人: Flocchini, Paola
• 金额: $ 2.4万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2016
• 资助国家: 加拿大
• 起止时间: 2016-01-01 至 2017-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=593795
• 关键词: Computational; issues; systems; mobile; entities

In this project I am interested in the design of deterministic algorithms for groups of computational moving entities. Such entities are identical, extremely simple and individually quite weak; but collectively capable of performing possibly complex tasks. The environment in which the entities operate can be a network or a terrain. In both environments the behaviour of the entities is cyclic: an entity becomes active (asynchronously and independently), it decides where to move based on the protocol, it moves to a location, and it becomes inactive again. What can be done by a team of entities and how efficiently depends on the characteristics of the entities like, for example, their communication media, their ability to see neighbouring entities, their level of synchronization, the possibility to remember the past. Some of the entities' characteristics (for example, locality, obliviousness, and communication) are particularly important and their study could have significant consequences in terms of scalability, efficiency, and fault-tolerance.

在这个项目中，我感兴趣的是为计算移动实体组设计确定性算法。这些实体是相同的，非常简单，单独相当弱;但集体能够执行可能复杂的任务。实体操作的环境可以是网络或地形。在这两种环境中，实体的行为都是循环的：一个实体变得活跃（异步和独立），它根据协议决定移动到哪里，它移动到一个位置，然后它再次变得不活跃。一组实体可以做什么以及效率如何取决于实体的特性，例如它们的通信媒体，它们看到相邻实体的能力，它们的同步水平，记住过去的可能性。一些实体的特征（例如，局部性、遗忘性和通信）特别重要，它们的研究可能在可扩展性、效率和容错性方面产生重大影响。