Calculabilité et complexité en distribué – DISPLEXITY

Nous avons obtenu des avances significatives pour une théorie de la complexité pour les calculs distribués.

Nous avons montré que l’ensemble des tâches qui peuvent être vérifiées par « yes/no » est limité. Nous avons donné une caractérisation complète des tâches qui peuvent être vérifiées dans les systèmes asynchrones avec mémoire partagée avec défaillances. En particulier de nombreuses tâches fondamentales comme le consensus ne peuvent être vérifiées dans ce sens. Nous explorons actuellement d’autres sémantiques possibles pour la vérification des tâches dans le but de capturer l’information minimale que les processus doivent échanger pour vérifier les tâches classiques.


Concernant les oracles de type « failure detectors », on a étendu des résultats connus concernant les modèles dans lesquels chaque processus a une identité unique à des modèles anonymes ou à des modèles avec homonymes. Ces résultats permettent une meilleure compréhension des difficultés à maitriser en même temps d’une part l’asynchronisme et les défaillances et d’autre part l’anonymat.
On a aussi proposé une nouvelle manière d’utiliser un oracle de type failure detectors pour résoudre une tâche distribuée « wait-free ».


Dans les modèles à mémoire partagée, une question intéressante est de déterminer quelles tâches peuvent être résolues si n processus partagent seulement n (ou même moins de n) multi-writer, multi-reader registres (MWMR). Pour cela on considère la complexité en nombre de tels registres pour un problème donné.On a montré que toute tâche qui peut être résolue avec n processus peut l’être avec seulement n MWMR registres et aussi que des tâches comme le set-consensus peuvent être résolues avec moins de n tels registres.

Les articles « Distributed Verification and hardness of Distributed Approximation » SICOMP dans SICOMP et « Towards a Complexity Theory for Local Distributed Computing » dans JACM fournissent une première tentative pour une théorie de la complexité du calcul distribué

Les premières résultats sont prometteurs. Les travaux concernant la tache «nouveaux modèles de calculs « sont en peu en retrait et npus comptons y porter nos efforts.

( sous ensemble des productions scientifiques)
Pierre Fraigniaud, Sergio Rajsbaum, Corentin Travers. Locality and Checkability in Wait-Free Computing. Distributed Computing, Springer Verlag, 2013.
The Weakest Failure Detector to Implement a Register in Asynchronous Systems with Hybrid Communication, TCS (2012). Damien Imbs et Michel Raynal
Anonymous asynchronous systems: the case of failure detectors, Distributed Computing (Springer), 2012, François Bonnet et Michel Raynal.
Power and limits of distributed computing shared memory models. Theoretical Computer Science, 2013. M. P. Herlihy, S. Rajsbaum and M. Raynal
Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5): 1235-1265 (2012) Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer.
5. Liah Kor, Amos Korman, David Peleg: Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification. Theory Comput. Syst. 53(2): 318-340 (2013)
Controller and estimator for dynamic networks. Inf. Comput. 223: 43-66 (2013) Amos Korman, Shay Kutten.
Towards a Complexity Theory for Local Distributed Computing. Journal of the ACM (JACM, To appear.) P. Fraigniaud, A. Korman, and D. Peleg.
Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge. Distributed Computing (DC- To appear). A. Korman, J. S. Sereni, and L. Viennot.

Le calcul distribué soulève de nombreuses questions de calculabilité et de complexité. Par exemple, pour les problèmes liés aux calculs tolérants aux pannes, les résultats classiques d’impossibilité ne sont pas liés à la puissance de calcul des processus. Ces résultats d’impossibilité ont une forme d’indécidabilité qui est fondamentalement différente de celle du calcul séquentiel. De la même manière, dans le calcul réseau, la possibilité de résoudre localement certaines tâches ne dépend pas de la puissance de chacun des processus.

L’objectif principal de DISPLEXITY(pour calcul DIStribué : calculabilité et comPLEXITé) est d’établir les fondements scientifiques d’une théorie de la calculabilité et de la complexité du calcul distribué.

Une difficulté à laquelle doit faire face DISPLEXITY est de concilier les deux sous communautés, calcul tolérant aux pannes et calcul réseau, qui ont chacune développé des modèles de calcul distribué. En effet la communauté du calcul distribué est séparée en deux sous communautés, pas nécessairement disjointe. La première est plus intéressée par les problèmes liés à l’asynchronisme et la deuxième par les problèmes liés au réseau. Les différents travaux auxquels s’attaquent ces deux communautés impliquent différents objectifs : la calculabilité est au centre de la première tandis que la complexité est au centre de la seconde.

Dans DISPLEXITY, la réconciliation de ces deux communautés sera réalisée en se concentrant sur la même classe de problèmes, les problèmes oui/non pour lesquels les calculs distribués seront interprétés comme une sortie binaire unique : oui ou non. La force de DISPLEXITY est de réunir les spécialistes des deux courants principaux de calcul distribué. DISPLEXITY profitera ainsi de l'expérience accumulée au cours de la dernière décennie par les deux communautés qui ont ainsi acquis une profonde compréhension des défis auxquels faire face pour créer une théorie de la complexitédistribué.
Pour atteindre ses objectifs, DISPLEXITY se propose de réaliser les tâches suivantes :
- Formaliser les problèmes oui/non dans le contexte du calcul distribué. Ces problèmes aspirent à jouer pour le calcul distribué un rôle analogue à celui joué par des problèmes de décision dans le contexte du calcul séquentiel.
- Revisiter les différentes notions d’oracles, qu’ils soient explicites (par exemple, des détecteurs de défaillances) ou implicites (par exemple, des informations a priori) utilisés dans le calcul distribué, pour les spécifier en terme de classes de décidabilité/complexité basées sur des oracles.
- Comparer des classes de complexité et de décidabilité correspondant à la capacité de résoudre des problèmes oui/non, ou de résoudre ces problèmes dans un certain temps. Cette tâche exige d’introduire de nouvelles notions de réductions entre problèmes.
- Identifier l'impact du non déterminisme sur le calcul distribué. En particulier DISPLEXITY vise à mieux comprendre le manque apparent d'impact du non déterminisme dans le contexte du calcul tolérant aux pannes, apparemment en contraste avec l'impact énorme du non déterminisme dans le contexte de calcul réseau. Egalement, nous pensons que le non déterminisme permettra la comparaison de classes de complexité définies dans le contexte de tolérance aux pannes avec des classes de complexité définies dans le contexte du calcul de réseau.
- Pour conclure, DISPLEXITY se concentrera sur des nouveaux paradigmes de calcul, y compris, le calcul distribué quantique et la théorie algorithmique des jeux (par exemple, des jeux de construction de réseau).

Le projet aura à faire face et à résoudre plusieurs problèmes extrêmement stimulants. Pour se faire, nous avons pris soin de rassembler dans DISPLEXITY de réunir des chercheurs français choisis parmi les leaders mondiaux du Calcul Distribué.
Le succès du projet aboutira à un accroissement significatif de la connaissance actuelle et de la compréhension du calcul distribué.