The Next 700 Impossibility Results in Time-Varying Graphs

Abstract : We address highly dynamic distributed systems modeled by time-varying graphs (TVGs). We interest in proof of impossibility results that often use informal arguments about convergence. First, we provide a distance among TVGs to define correctly the convergence of TVG sequences. Next, we provide a general framework that formally proves the convergence of the sequence of executions of any deterministic algorithm over TVGs of any convergent sequence of TVGs. Finally, we illustrate the relevance of the above result by proving that no deterministic algorithm exists to compute the underlying graph of any connected-over-time TVG, i.e., any TVG of the weakest class of long-lived TVGs.
Type de document :
Rapport
[Research Report] UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL. 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01097109
Contributeur : Swan Dubois <>
Soumis le : jeudi 18 décembre 2014 - 19:43:05
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:28:55

Fichiers

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

Identifiants

  • HAL Id : hal-01097109, version 1
  • ARXIV : 1412.6007

Collections

Citation

Nicolas Braud-Santoni, Swan Dubois, Mohamed Hamza Kaaouachi, Franck Petit. The Next 700 Impossibility Results in Time-Varying Graphs. [Research Report] UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL. 2014. 〈hal-01097109〉

Partager

Métriques

Consultations de la notice

466

Téléchargements de fichiers

153