David ILCINKAS
David Ilcinkas Chargé de Recherches (CNRS)

Équipe LaBRI : Combinatoire et Algorithmique
Équipe projet commune INRIA-LaBRI : CEPAGE
Fonction administrative : Correspondant BMI et SCD. Resp. Adj de l'Equipe CombiAlgo
Page personnelle : http://www.labri.fr/~ilcinkas/
Courrier électronique : david.ilcinkasarobaselabri.fr
Bureau : 361
Tél : +33 (0)5 40 00 69 12


Recherche

Ma thèse de doctorat a porté sur la complexité en espace du problème de l'exploration de graphes : un agent mobile se déplace de sommet en sommet le long des arêtes d'un graphe dont il ignore la structure, et a pour tâche de visiter au moins une fois tous les sommets du graphe. Ce problème est motivé par ses applications en logique, complexité, et bien sûr en robotique. Mes recherches se sont depuis étendues au calcul par agents mobiles et au domaine de l'algorithmique répartie en général. Je porte souvent dans mes travaux un intérêt particulier aux liens entre la quantité de mémoire disponible d'une part et l'existence et l'efficacité de solutions au problème étudié d'autre part.


Principales publications:

[ACM TALG 2008]
Alors qu'aucun agent mobile de mémoire constante n'est capable d'explorer tous les graphes, mêmes planaires de degré maximum~3, cet article montre qu'il existe un agent mobile de mémoire constante et un algorithme coloriant les sommets de tout graphe en seulement trois couleurs tels que cet agent explore avec succès tout graphe ainsi colorié.

[JCSS 2009]
Cet article introduit la notion de conseil comme mesure de la difficulté de problèmes du calcul distribué. Le concept de conseil permet d'étudier quantitativement l'impact des connaissances données aux n{\oe}uds du réseau sur les performances que ces n{\oe}uds peuvent atteindre pour résoudre un problème donné. Dans cet article, nous appliquons cet outil aux tâches apparemment similaires du réveil et de la diffusion (en utilisant un nombre linéaire de messages) pour montrer une différence quantitative de difficulté entre celles-ci.

[DISC 2008]
Un trou noir est un n{\oe}ud d'un réseau qui détruit tout agent y entrant sans laisser de trace détectable. L'emplacement du trou noir doit être déterminé par une une équipe d'agents mobiles identiques déployée à partir d'un emplacement sain. Nous prouvons dans cet article que, pour ce problème, le modèle des cailloux idéaux (un caillou ne peut être placé que sur les n{\oe}uds, et pas plus d'un caillou ne peut être placé sur un n{\oe}ud donné) est aussi puissant que le modèle des tableaux blancs (zone de mémoire présente sur chaque n{\oe}ud accessible en lecture/écriture).

Extrait de publications


Evangelos Bampas, Leszek Gąsieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, et al.. Robustness of the Rotor–Router Mechanism. Algorithmica, Springer Verlag, 2017, 78 (3), pp.869-895.

Christian Glacet, Nicolas Hanusse, David Ilcinkas, Colette Johnen. Disconnected components detection and rooted shortest-path tree maintenance in networks - extended version. [Research Report] LaBRI, CNRS UMR 5800. 2016.

Cyril Gavoille, David Ilcinkas. Proceedings of the 30th International Symposium on Distributed Computing (DISC 2016). France. 9888, Springer, 2016, Lecture Notes in Computer Science (ARCoSS),

Stéphane Devismes, David Ilcinkas, Colette Johnen. Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps. Panagiota Fatourou and Ernesto Jiménez and Fernando Pedone. 20th International Conference on Principles of Distributed Systems (OPODIS 2016), Dec 2016, Madrid, Spain. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 70, pp.10:1-10:16, 2017, Leibniz International Proceedings in Informatics (LIPIcs).

Evangelos Bampas, David Ilcinkas. On Mobile Agent Verifiable Problems. Latin American Theoretical Informatics Symposium (LATIN 2016), Apr 2016, Ensenada, Mexico. Springer, 9644, pp.123-137, LATIN 2016: Theoretical Informatics 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings.


Page mise à jour le 13/08/2010 à 10:56