Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems

Abstract : We address the problem of computing a Minimal Dominating Set in highly dynamic distributed systems. We assume weak connectivity, i.e., the network may be disconnected at each time instant and topological changes are unpredictable. We make only weak assumptions on the communication: every process is infinitely often able to communicate with other processes (not necessarily directly). Our contribution is threefold. First, we propose a new definition of minimal dominating set suitable for the context of time-varying graphs that seems more relevant than existing ones. Next, we provide a necessary and sufficient topological condition for the existence of a deterministic algorithm for minimal dominating set construction in our settings. Finally, we propose a new measure of time complexity in time-varying graph in order to to allow fair comparison between algorithms. Indeed, this measure takes account of communication delays attributable to dynamicity of the graph and not to the algorithms.
Type de document :
Rapport
[Research Report] UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL. 2015
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01111610
Contributeur : Swan Dubois <>
Soumis le : dimanche 1 février 2015 - 21:55:36
Dernière modification le : jeudi 11 janvier 2018 - 06:27:33
Document(s) archivé(s) le : mercredi 27 mai 2015 - 15:02:08

Fichiers

RR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01111610, version 1
  • ARXIV : 1502.00378

Collections

Citation

Swan Dubois, Mohamed Hamza Kaaouachi, Franck Petit. Enabling Minimal Dominating Set in Highly Dynamic Distributed Systems. [Research Report] UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL. 2015. 〈hal-01111610〉

Partager

Métriques

Consultations de la notice

236

Téléchargements de fichiers

134