Local Distributed Decision and Verification
Décision et vérification distribuées dans le modèle local
Résumé
This thesis lays in the context of distributed computing on networks, and more particularly
on the locality aspects that appear in that context. By the systematic study
of decision problems, we introduce the complexity classes ULD and UNLD for local
decision and verication respectively, and give separation results describing a hierarchy
involving other classes of local decision in the literature. These results are
accompanied by a classication of several distributed problems based on the hierarchy
we introduce. We examine and discuss two key ingredients in local decision and
verication: the interpretation function on the outputs, and node identication.
In this thesis, we also isolate the aspect of locality by studying it through the
prism of the non-signaling model, which, even though not realistic, oers interesting
theoretical possibilities, including the derivation of lower bounds for distributed
quantum computing without having to manipulate objects of that theory. Finally,
by placing ourselves at the extreme limit of locality constraints, we consider the particular
class of two-player games in absence of any communication and examine the
limits of quantum distributed computing for this class of games.
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.
Loading...