📖
On peut tromper mille personnes mille fois, mais pas plus
Lélia Blin, Anaïs Durand, Sébastien Tixeuil

On peut tromper mille personnes mille fois, mais pas plus

Science & Mathematics Published 2020 Verification Pending

Overview & Synopsis

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.

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title On peut tromper mille personnes mille fois, mais pas plus
Author / Organization Lélia Blin, Anaïs Durand, Sébastien Tixeuil
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2020
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-195403
Original Source Link Visit Source Page on hal.science »