Consider a team of mobile computational entities, called agents, operating in a networked environment. To cooperatively solve problems and perform assigned tasks, the agents need to coordinate and communicate. The interaction mechanisms available to the agents have a strong impact on both computability and complexity. In the literature, a wide range of communication mechanisms have been explored, ranging from powerful options that require significant system resources (such as whiteboards) to very basic and cost-effective methods, like identical passive objects known as tokens. While algorithms that use whiteboards can effectively and explicitly communicate complex and resource-intensive information (like network maps), protocols that rely on token manipulation avoid to perform complex communication. Instead, they employ coordination and limited communication in an ad-hoc and implicit manner. The contribution of this paper consists in the design of simple, efficient communication protocols employing only tokens (and space). These protocols can be used as subroutines for explicitly communicating complex information in systems providing only token-based communication. This allows designers of token-based algorithms to explicitly employ complex communication between agents, enhancing their design freedom and flexibility. Additionally, our protocols facilitate the translation of results from models that depend solely on face-to-face communication to those that operate without such interactions but use tokens instead.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Explicit Token-Based Communication for Mobile Entities

  • Balasingham Balamohan,
  • Stefan Dobrev,
  • Paola Flocchini,
  • Nicola Santoro

摘要

Consider a team of mobile computational entities, called agents, operating in a networked environment. To cooperatively solve problems and perform assigned tasks, the agents need to coordinate and communicate. The interaction mechanisms available to the agents have a strong impact on both computability and complexity. In the literature, a wide range of communication mechanisms have been explored, ranging from powerful options that require significant system resources (such as whiteboards) to very basic and cost-effective methods, like identical passive objects known as tokens. While algorithms that use whiteboards can effectively and explicitly communicate complex and resource-intensive information (like network maps), protocols that rely on token manipulation avoid to perform complex communication. Instead, they employ coordination and limited communication in an ad-hoc and implicit manner. The contribution of this paper consists in the design of simple, efficient communication protocols employing only tokens (and space). These protocols can be used as subroutines for explicitly communicating complex information in systems providing only token-based communication. This allows designers of token-based algorithms to explicitly employ complex communication between agents, enhancing their design freedom and flexibility. Additionally, our protocols facilitate the translation of results from models that depend solely on face-to-face communication to those that operate without such interactions but use tokens instead.