The Next 700 Impossibility Results in Time-Varying Graphs
| Autor: | Swan Dubois, Mohamed Hamza Kaaouachi, Franck Petit, 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), UPMC Sorbonne Universités/CNRS/Inria - EPI REGAL, 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 de Paris, Dubois, Swan |
| Jazyk: | angličtina |
| Rok vydání: | 2014 |
| Předmět: |
FOS: Computer and information sciences
Sequence Class (set theory) Theoretical computer science Deterministic algorithm Computer science Proof of impossibility 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science - Distributed Parallel and Cluster Computing 010201 computation theory & mathematics Convergence (routing) [INFO.INFO-DC] Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] 0202 electrical engineering electronic engineering information engineering Limit of a sequence 020201 artificial intelligence & image processing Relevance (information retrieval) Distributed Parallel and Cluster Computing (cs.DC) Impossibility [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Algorithm |
| Zdroj: | [Research Report] UPMC Sorbonne Universités/CNRS/Inria-EPI REGAL. 2014 International Journal of Networking and Computing International Journal of Networking and Computing, Higashi Hiroshima : Dept. of Computer Engineering, Hiroshima University, 2016, 6 (1), pp.27-41 International Journal of Networking and Computing, 2016, 6 (1), pp.27-41 |
| ISSN: | 2185-2839 2185-2847 |
| Popis: | International audience; We consider highly dynamic distributed systems modelled by time-varying graphs (TVGs). We first address proof of impossibility results that often use informal arguments about convergence. 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. Next, we focus of the weakest class of long-lived TVGs, i.e., the class of TVGs where any node can communicate any other node infinitely often. We illustrate the relevance of our result by showing that no deterministic algorithm is able to compute various distributed covering structure on any TVG of this class. Namely, our impossibility results focus on the eventual footprint, the minimal dominating set and the maximal matching problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|