On peut tromper mille personnes mille fois, mais pas plus
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.
hal.science)
← / → 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 » |