The gathering of two or more agents in a graph is an important problem in the area of distributed computing and has been extensively studied especially for the fault free scenario. In this paper we consider the mobile agents gathering problem in the presence of an adversarial malicious agent which by occupying an empty node might prevent honest agents from entering this node. The honest agents move in synchronous rounds and at each round an agent can move to an adjacent node only if this node is not occupied by the malicious agent. We model the honest agents as identical finite state automata moving in an anonymous oriented grid topology and having no information about the size of the graph, while the malicious agent is assumed to be arbitrarily fast and to have full knowledge of the locations and the strategy of the honest agents at all times. The agents cannot leave messages at nodes or communicate with each-other unless they meet at a node. Previous studies consider the problem for ring networks and for asynchronous grids, where rendezvous was solved only for the special case of agents starting already in connected configurations. In this paper, we study the problem for synchronous agents in anonymous oriented grid networks for any starting configuration without multiplicities and any number of agents. We first show that rendezvous is impossible for 2 agents even when the agents can see the locations of each-other at all times, while 3 agents can gather if they have global visibility. We then present a universal deterministic algorithm that solves the problem for 4 or more agents having only local visibility and constant memory, in any oriented grid with a malicious mobile adversary.

The gathering of two or more agents in a graph is an important problem in the area of distributed computing and has been extensively studied especially for the fault free scenario. In this paper we consider the mobile agents gathering problem in the presence of an adversarial malicious agent which by occupying an empty node might prevent honest agents from entering this node. The honest agents move in synchronous rounds and at each round an agent can move to an adjacent node only if this node is not occupied by the malicious agent. We model the honest agents as identical finite state automata moving in an anonymous oriented grid topology and having no information about the size of the graph, while the malicious agent is assumed to be arbitrarily fast and to have full knowledge of the locations and the strategy of the honest agents at all times. The agents cannot leave messages at nodes or communicate with each-other unless they meet at a node. Previous studies consider the problem for ring networks and for asynchronous grids, where rendezvous was solved only for the special case of agents starting already in connected configurations. In this paper, we study the problem for synchronous agents in anonymous oriented grid networks for any number of agents starting in distinct locations. We first show that rendezvous is impossible for 2 agents even when the agents can see the locations of each-other at all times, while 3 agents can gather if they have global visibility. We then present a universal deterministic algorithm that solves the problem for 4 or more agents having only local visibility and constant memory, in any oriented grid with a malicious mobile adversary.

Gathering of Robots in a Grid with Mobile Faults

Flaminia L. Luccio;
2019

Abstract

The gathering of two or more agents in a graph is an important problem in the area of distributed computing and has been extensively studied especially for the fault free scenario. In this paper we consider the mobile agents gathering problem in the presence of an adversarial malicious agent which by occupying an empty node might prevent honest agents from entering this node. The honest agents move in synchronous rounds and at each round an agent can move to an adjacent node only if this node is not occupied by the malicious agent. We model the honest agents as identical finite state automata moving in an anonymous oriented grid topology and having no information about the size of the graph, while the malicious agent is assumed to be arbitrarily fast and to have full knowledge of the locations and the strategy of the honest agents at all times. The agents cannot leave messages at nodes or communicate with each-other unless they meet at a node. Previous studies consider the problem for ring networks and for asynchronous grids, where rendezvous was solved only for the special case of agents starting already in connected configurations. In this paper, we study the problem for synchronous agents in anonymous oriented grid networks for any starting configuration without multiplicities and any number of agents. We first show that rendezvous is impossible for 2 agents even when the agents can see the locations of each-other at all times, while 3 agents can gather if they have global visibility. We then present a universal deterministic algorithm that solves the problem for 4 or more agents having only local visibility and constant memory, in any oriented grid with a malicious mobile adversary.
International Conference on Current Trends in Theory and Practice of Informatics
File in questo prodotto:
File Dimensione Formato  
DGLM.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 232.31 kB
Formato Adobe PDF
232.31 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/3707153
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact