[CoA] David ILCINKAS (2012.11.22)
- il y a 11 ans
Premières journées du GT CoA Complexité et Algorithmes du GdR IM
21-22 novembre, ESPCI, Paris 5ème
--
Connaissance initiale et résultats d'impossibilité en algorithmique distribuée
par David ILCINKAS (LaBRI)
--
Résumé (Fr).
Dans le cadre de l'algorithmique distribuée, un processus ne connaît généralement pas exactement l'instance du problème lorsqu'il démarre son exécution. Ainsi de nombreux algorithmes distribuées supposent que chaque processus dispose initialement d'une certaine connaissance sur l'instance, par exemple une borne supérieure sur la taille du réseau. Pour certains problèmes, il semble que l'absence d'un certain type de connaissance initiale rende le problème impossible à résoudre. Nous nous intéresserons dans cet exposé à des formalisations possibles du concept de connaissance initiale qui permettraient de pouvoir prouver de tels résultats d'impossibilité.
--
Initial knowledge and impossibility results in distributed computing
by David ILCINKAS (LaBRI)
--
Abstract (EN). In the distributed computing framework, a process does not generally know the whole instance of the problem when it starts its execution. Numerous distributed algorithms so assume that each process is initially provided with some piece of knowledge about the instance, like an upper bound on the total number of processes. For some problems, it seems that the lack of some kind of initial knowledge makes the problem impossible to solve. In this talk, we will be interested in how to formalize the concept of initial knowledge such that it would allow to formally prove such impossibility results.
21-22 novembre, ESPCI, Paris 5ème
--
Connaissance initiale et résultats d'impossibilité en algorithmique distribuée
par David ILCINKAS (LaBRI)
--
Résumé (Fr).
Dans le cadre de l'algorithmique distribuée, un processus ne connaît généralement pas exactement l'instance du problème lorsqu'il démarre son exécution. Ainsi de nombreux algorithmes distribuées supposent que chaque processus dispose initialement d'une certaine connaissance sur l'instance, par exemple une borne supérieure sur la taille du réseau. Pour certains problèmes, il semble que l'absence d'un certain type de connaissance initiale rende le problème impossible à résoudre. Nous nous intéresserons dans cet exposé à des formalisations possibles du concept de connaissance initiale qui permettraient de pouvoir prouver de tels résultats d'impossibilité.
--
Initial knowledge and impossibility results in distributed computing
by David ILCINKAS (LaBRI)
--
Abstract (EN). In the distributed computing framework, a process does not generally know the whole instance of the problem when it starts its execution. Numerous distributed algorithms so assume that each process is initially provided with some piece of knowledge about the instance, like an upper bound on the total number of processes. For some problems, it seems that the lack of some kind of initial knowledge makes the problem impossible to solve. In this talk, we will be interested in how to formalize the concept of initial knowledge such that it would allow to formally prove such impossibility results.