Affordable Access

Silence dans la forêt !

Authors
  • Altisen, Karine
  • Devismes, Stéphane
  • Durand, Anaïs
Publication Date
Jun 04, 2019
Source
HAL
Keywords
Language
French
License
Unknown
External links

Abstract

Nous formalisons des schémas d'algorithmes distribués, classiquement utilisés en autostabilisation, afin d'obtenir des résultats généraux relatifs à leur correction et leur complexité. Précisément, nous étudions une classe d'algorithmes dédiés aux réseaux munis d'un sens de direction décrivant une forêt couvrante. La définition de cette classe est simple au sens où elle est quasi-syntaxique. Tous les algorithmes de cette classe sont (1) autostabilisants et silencieux, et (2) ont un temps de stabilisation à la fois polynomial en mouvements et asymptotiquement optimal en rondes. Pour illustrer la polyvalence de notre méthode, nous passons en revue plusieurs travaux où nos résultats s'appliquent.

Report this publication

Statistics

Seen <100 times