Skip to Main content Skip to Navigation
Theses

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.
Complete list of metadatas

Cited literature [76 references]  Display  Hide  Download

https://hal.inria.fr/tel-01274154
Contributor : Laurent Viennot <>
Submitted on : Monday, February 15, 2016 - 2:51:19 PM
Last modification on : Saturday, March 28, 2020 - 2:13:59 AM
Document(s) archivé(s) le : Saturday, November 12, 2016 - 9:20:59 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

236

Files downloads

208