A Generic Framework for Impossibility Results in Time-Varying Graphs
| Autor: | Mohamed-Hamza Kaaouachi, Franck Petit, Swan Dubois, Nicolas Braud-Santoni |
|---|---|
| Přispěvatelé: | Graz University of Technology [Graz] (TU Graz), Large-Scale Distributed Systems and Applications (Regal), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Pierre et Marie Curie - Paris 6 - UFR de Médecine Pierre et Marie Curie (UPMC), Université Pierre et Marie Curie - Paris 6 (UPMC) |
| Rok vydání: | 2015 |
| Předmět: |
Theoretical computer science
Computer science Deterministic algorithm Proof of impossibility Voltage graph Graph underlying graph Limit of a sequence [INFO]Computer Science [cs] Time-Varying Graph Impossibility [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Impossibility results Algorithm |
| Zdroj: | Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International 17th Workshop on Advances on Parallel and Distributed Processing Symposium (APDCM'15) 17th Workshop on Advances on Parallel and Distributed Processing Symposium (APDCM'15), May 2015, Hyderabad, India. pp.483-489, ⟨10.1109/IPDPSW.2015.59⟩ IPDPS Workshops |
| DOI: | 10.1109/IPDPSW.2015.59⟩ |
| Popis: | We address highly dynamic distributed systems modelled by time-varying graphs (TVGs). We are interested in proof of impossibility results that often use informal arguments about convergence. First, we provide a topological distance metric over sets of TVGs to correctly define the convergence of TVG sequences in such sets. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|