Local Distributed Decision and Verification

Heger Arfaoui 1, 2
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Résumé : Cette thèse s'inscrit dans le contexte du calcul distribué sur les réseaux, et, plus particulièrement, sur les aspects de localité qui apparaissent dans ce cadre. Par l'étude systématique des problèmes de décision, nous introduisons les classes de complexité ULD et UNLD pour la décision et la vérification locale, et présentons des résultats de séparation décrivant une hiérarchie impliquant d'autres classes relatives à la littérature de la décision locale. Ces résultats sont accompagnés de la classification de plusieurs problèmes distribués selon la hiérarchie introduite. Nous examinons et discutons dans ce cadre deux ingrédients ayant un rôle clé dans la décision et la vérification locale : la fonction d'interprétation des sorties, et l'identification des noeuds du réseau. Nous isolons également dans cette thèse l'aspect de la localité en l'étudiant sous le prisme du modèle "non-signalling", qui bien que n'étant pas un modèle réaliste, ouvre des possibilités théoriques intéressantes, notamment sur la dérivation de bornes inférieures pour le calcul distribué quantique, sans avoir à manipuler les objets de cette théorie. Finalement, en nous plaçant à la limite extrême des contraintes de localité, nous considérons la classe particulière de jeux à deux joueurs en l'absence de communication, et examinons les limites du calcul distribué quantique pour cette classe de jeux.
Type de document :
Thèse
Networking and Internet Architecture [cs.NI]. Paris Diderot University, 2014. English
Liste complète des métadonnées

Littérature citée [76 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01274154
Contributeur : Laurent Viennot <>
Soumis le : lundi 15 février 2016 - 14:51:19
Dernière modification le : mardi 17 avril 2018 - 11:30:28
Document(s) archivé(s) le : samedi 12 novembre 2016 - 21:20:59

Identifiants

  • HAL Id : tel-01274154, version 1

Collections

Citation

Heger Arfaoui. Local Distributed Decision and Verification. Networking and Internet Architecture [cs.NI]. Paris Diderot University, 2014. English. 〈tel-01274154〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

69