Mathematical Methods in Distributed Computing – DISCMAT

Le projet est motivé par le sentiment que le potentiel des méthodes mathématiques, y compris
celles de la topologie combinatoire et algébrique, pour la théorie du calcul distribué n'est pas encore
bien compris. Bien qu'il existe des exemples lumineux et esthétiquement attrayants de la modélisation
des calculs distribués en tant que «complexes« simples (éléments de base de la topologie combinatoire),
la partie de l'informatique théorique répartie qui a été pénétrée par les méthodes mathématiques
rigoureuses est encore assez limitée ; même si les mathématiques ont été utiles, plusieurs résultats
existants peuvent être obtenus en utilisant le raisonnement algorithmique classique.

Sur le plan global, le projet comprend quatre modules de travail:

WP1. Modèles mathématiques pour l'informatique distribuée: un cadre de modélisation uniforme incorporant
des types de fautes, de communication et de synchronie plus généraux
que le crash classique, la lecture-écriture, modèle wait-fee.


WP2. Calculabilité distribuée: formuler et prouver un théorème de calculabilité généralisée,
paramétré par un complexe de protocole visant à modéliser les exécutions, les complexes
correspondant à la spécification du problème et la relation entre les deux.

WP3. Théorie mathématique motivée par l'informatique distribuée: ici, nous avons l'intention de
considérer les structures mathématiques issues des calculs distribués.


WP4. Conception d'algorithmes/protocoles: utilisez les résultats des trois premiers modules de
travail pour dériver les limites supérieures, ce qui se traduit par des protocoles explicites pour
les problèmes informatiques répartis.

WP1 et WP2: la relation entre le modèle byzantin, dans lequel les processus peuvent se comporter de manière
arbitraire, et le modèle de panne «bénigne« crash a été clarifié [DISC 2016]. L'algorithme de consensus byzantin
optimal (en termes de complexité et de temps de message), un bloc fondamental pour la construction de
systèmes distribués tolérants aux pannes, a été découvert [JACM 2016]. Des hypothèses minimales de
synchronie pour résoudre le consensus dans le modèle byzantin ont été trouvées [PODC 2015]. Ces résultats
pourraient aider à combler l'écart entre les modèles byzantins et les modèles de collision (plus compréhensibles).


Dans WP1 et WP2, nous avons obtenu quelques résultats très intéressants sur la caractérisation des modèles
génériques de calcul. La décidabilité du pouvoir relatif des collections consensuelles a été établie [OPODIS 2016].
Nous avons montré que la calculabilité d'une grande classe de modèles contradictoires équitables se caractérise
précisément par leurs fonctions d'accord [NETYS 2016] et établi que des adversaires justes (capture de classes
populaires d'adversaires superset-closed et symétriques) peuvent être exprimés sous une forme topologique
compacte [BA au DISC 2017]. Nous croyons que ce résultat est fondamental, car il montre le potentiel de la
capture de calculs illimités à longue durée de vie, en utilisant des primitives de communication sophistiquées,
grâce à des abstractions limitées finies simples.


Des résultats notables au sein de WP3 sont la dérivation d'un algorithme «explicite» pour la rupture de la
symétrie faible dans un système de dimension certaine (seule existait ne preuve existentielle de ce que l'on savait
jusqu'ici) et la preuve que toutes les identités binomiales sont ordonnables. Le résultat peut être appliqué
dans l'informatique distribuée pour dériver de nouvelles limites fortes sur la complexité ronde de la tâche
de rupture de symétrie faible.

Dans WP1 et WP2, notre prochaine étape consistera à étendre notre caractérisation topologique à des
classes de modèles plus généraux. Les modèles dans lesquels (a) les primitives génériques de synchronisation
ou (b) les collections d'objets définis par consensus sont utilisés présentent un intérêt particulier dans ce
. Nos résultats partiels et prometteurs sont ici: (1) une caractérisation topologique des modèles de
lecture-écriture avec des promoteurs de test et d'ensemble et (2) une caractérisation du pouvoir
relatif de la collecte de consensus dans la résolution. L'objectif immédiat est de construire une
caractérisation topologique générale sur ces résultats.


Une question intrigante reste: comment exprimer des algorithmes topologiquement impliquant des abstractions à longue durée de vie. Très peu de compréhension est atteinte jusqu'ici.


Dans WP3, nous avons des preuves que les modèles informatiques distribués et les tâches donnent lieu à des structures mathématiques intéressantes. Il serait intéressant d'explorer cela plus avant, en examinant peut-être les modèles généraux de mode et les problèmes de distribution de l'informatique.

Enfin, au sein de WP4, nous sommes encore perplexes sur le fait de savoir si la topologie combinatoire peut permettre une conception optimale des protocoles et nous avons l'intention d'aborder ce casse-tête.

Productions scientifiques et brevets

1. Plusieurs chercheurs ont été soutenus par le projet: Zohir Bouzid (post-doctorat à l'Université de Rennes 1), Thibault Rieutord (doctorant à Telecom ParisTech), Damien Imbs (postdoc à l'Université de Brême, soutenu par le projet DISCMAT au DFG côté).

2. Plusieurs publications très visibles (Journal of the ACM, JPDC, SIAM Journal on Computing ACM PODC, DISC, etc.): 24 articles de revues, 31 articles de conférence (avec rapporteurs)

3. Participation à de multiples manifestations scientifiques (DISC 2015, OPODIS 2015, séminaire Dagstuhl, séminaire Banff/CMO, DISC 2016, SSS 2016, OPODIS 2016, séminaire Banff 2016, NETYS 2017).

4. La 1ère école d'été sur la pratique et la théorie de l'informatique concurrente (SPTCC 2017) a été organisée par DISCMAT.