2013 | OriginalPaper | Buchkapitel
Gathering Asynchronous Oblivious Agents with Restricted Vision in an Infinite Line
verfasst von : Samuel Guilbault, Andrzej Pelc
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of gathering identical, memoryless, mobile agents in one node of an infinite anonymous line of nodes. Agents start from different nodes of the line. They operate in Look-Compute-Move cycles and have to end up at the same node. Our model differs from most of the existing literature on gathering asynchronous oblivious agents in graphs in that the agents have restricted perception capabilities: they can only see at bounded distance
d
(called the
radius of vision
) from their current location. In one cycle, an agent takes a snapshot of the part of the line at distance at most
d
from it (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent.
An initial configuration of agents is called
gatherable
if there exists a deterministic algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) A deterministic gathering algorithm is
universal
if it gathers all gatherable configurations. We observe that if the vision of agents is unrestricted then a universal gathering algorithm exists. For radius of vision
d
= 1 a universal gathering algorithm is known. By contrast, our main result shows that for any finite radius of vision
d
> 1 there is no universal gathering algorithm. Our result remains valid for rings of size at least 7
d
+ 8.