Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) ParSys
Distributed decision and verification by mobile agents
Evangelos Bampas

22 January 2019, 10h30 - 22 January 2019, 12h00
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Algorithmique distribuée

Résumé :
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 [J. Parallel Distrib. Comput, vol. 109, pp. 117–128], we introduce several natural new computability classes allowing for a finer classification of problems below MAV or its complement class co - MAV, the former being the class of problems that are verifiable when the agents are provided with an appropriate certificate. 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 may be 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.
(joint work with David Ilcinkas)

Pour en savoir plus : https://www.lri.fr/~bampas
Séminaires
Langage d'icônes et visualisation d'ensembles : mé
Thursday 24 October 2019 - 14h30
Salle : 475 - PCRI-N
Jean-Baptiste Lamy .............................................

Matchings and related structures with Specified Co
Théorie des graphes
Thursday 17 October 2019 - 14h30
Salle : 445 - PCRI-N
Yannis Manoussakis .............................................

Conservation of structural long-range modules in R
Thursday 17 October 2019 - 14h30
Salle : 475 - PCRI-N
Vladimir Reinharz .............................................

Overcoming interference in the beeping communicati
Algorithmique distribuée
Friday 11 October 2019 - 14h30
Salle : 445 - PCRI-N
Fabien Dufoulon .............................................

Local checkability: a notion that started in the c
Algorithmique distribuée
Tuesday 08 October 2019 - 11h00
Salle : 465 - PCRI-N
Prof. Kutten Shay .............................................