On peut tromper mille personnes mille fois, mais pas plus - Université Clermont Auvergne Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

On peut tromper mille personnes mille fois, mais pas plus

Résumé

Nous explorons la possibilité de concevoir des algorithmes auto-stabilisants pour des systèmes distribués à passage de messages où l'adversaire peut initialement placer un nombre arbitraire de messages corrompus (leur contenu est également déterminé par l'adversaire) dans les canaux de communications. Plus précisément, nous proposons un algorithme auto-stabilisant de (∆ + 1)-coloration pour un graphe arbitraire de degré maximum ∆ dans le modèle à passage de messages asynchrone. Cet algorithme est déterministe et converge en O(k ∆ n 2 log n) échanges de messages, où k est une borne sur la capacité des canaux de communications et n est le nombre de processus. Notre algorithme utilise des messages de O(log log n + log ∆) bits et une mémoire de O(∆ log ∆ + log log n) bits par processus. La propriété fondamentale de notre algorithme est le fait que les processus ne nécessitent aucune connaissance sur le nombre de messages initialement présents dans les canaux (k est inconnu). Pour concevoir notre protocole de coloration, nous utilisons une construction auto-stabilisante de graphe orienté acyclique couvrant, qui peut également servir d'outil pour résoudre d'autres tâches dans le même contexte.
Fichier principal
Vignette du fichier
ALGOTEL20-2.pdf (110.05 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03746708 , version 1 (05-08-2022)

Identifiants

  • HAL Id : hal-03746708 , version 1

Citer

Lélia Blin, Anaïs Durand, Sébastien Tixeuil. On peut tromper mille personnes mille fois, mais pas plus. ALGOTEL 2020 - 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. pp.156-165. ⟨hal-03746708⟩
188 Consultations
79 Téléchargements

Partager

Gmail Facebook X LinkedIn More