We are receiving Evangelos Bampas from Aix-Marseille University – Laboratoire d’Informatique Fondamentale de Marseille (LIF). He will give a talk on Wednesday, March 23 at 14:00 in room Turing.
Title: On mobile agent verifiable problems
Abstract:
We consider decision problems that are solved in a distributed fashion by synchronous mobile agents operating in an unknown, anonymous network. Each agent has a unique identifier and an input string and they have to decide collectively a property which may involve their input strings, the graph on which they are operating, and their particular starting positions. Building on recent work by Fraigniaud and Pelc [LATIN 2012], we introduce several new and natural computability classes allowing for a finer classification of problems below co-MAV or MAV, the latter being the class of decision problems that are verifiable when an appropriate certificate is distributed to the agents. We provide inclusion and separation results among all these classes. We also determine their closure properties with respect to set-theoretic operations. Our main technical tool, which is of independent interest, is a new meta-protocol that enables the execution of a possibly infinite number of mobile agent protocols essentially in parallel, similarly to the well-known dovetailing technique from classical computability theory.
Bio:
Evangelos Bampas is a postdoctoral researcher in LIF, Aix-Marseille University. Previously, he has worked in LaBRI, University of Bordeaux, in the School of Electrical and Computer Engineering of the National Technical University of Athens in Greece, and in LIP6, Pierre and Marie Curie University (Paris 6). He received his doctorate in Electrical and Computer Engineering from the National Technical University of Athens under the supervision of Prof. Stathis Zachos. His research interests include distributed computing with an emphasis on mobile agent computing, and wavelength assignment problems in optical networks.
Evangelos’ personal page: http://www.corelab.ntua.gr/~ebamp