Vérification de preuves distribuées : compromis temps-espace

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry

Algotel 2019: 21èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Juin 2019, Saint Laurent de la Cabrerisse, France.
hal:02118043

Une preuve distribuée est un mécanisme permettant aux nœuds d'un réseau de décider collectivement et efficacement si le réseau est dans une configuration correcte, par rapport à un certain prédicat. La vérification de ces preuves est généralement faite en un nombre constant de rondes. Dans cet article nous étudions l'impact d'un temps de vérification non-constant sur la taille des preuves.

J'ai reçu le prix du meilleur article étudiant à Algotel 2019 pour la présentation de ce résultat. Le prix a aussi été attribué Jason Schoeters.