Decidability classes for mobile agents computing

Pierre Fraigniaud 1 Andrzej Pelc 2
1 GANG - Networks, Graphs and Algorithms
Inria de Paris, IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
Abstract : We establish a classification of decision problems that are to be solved by mobile agents operating in unlabeled graphs, using a deterministic protocol. The classification is with respect to the ability of a team of agents to solve decision problems, possibly with the aid of additional information. In particular, our focus is on studying differences between the decidability of a decision problem by agents and its verifiability when a certificate for a positive answer is provided to the agents (the latter is to the former what NP is to P in the framework of sequential computing). We show that the class MAV of mobile agents verifiable problems is much wider than the class MAD of mobile agents decidable problems. Our main result shows that there exist natural MAV-complete problems: the most difficult problems in this class, to which all problems in MAV are reducible via a natural mobile computing reduction. Beyond the class MAV we show that, for a single agent, three natural oracles yield a strictly increasing chain of relative decidability classes.
Complete list of metadatas

https://hal.inria.fr/hal-01674623
Contributor : Pierre Fraigniaud <>
Submitted on : Wednesday, January 3, 2018 - 11:52:01 AM
Last modification on : Friday, December 13, 2019 - 11:18:02 AM

Links full text

Identifiers

Collections

Citation

Pierre Fraigniaud, Andrzej Pelc. Decidability classes for mobile agents computing. Journal of Parallel and Distributed Computing, Elsevier, 2017, 109, pp.117-128. ⟨10.1016/j.jpdc.2017.04.003⟩. ⟨hal-01674623⟩

Share

Metrics

Record views

141