The Next 700 Impossibility Results in Time-Varying Graphs
The Next 700 Impossibility Results in Time-Varying Graphs
复制标题
接下来 700 个不可能的结果会出现在时变图中
DOI：
10.15803/ijnc.6.1_27
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
F. Petit
中科院分区：
文献类型：
--
作者：
Nicolas Braud;S. Dubois;Mohamed;F. Petit
我们研究由时变图(TVG)建模的高度动态的分布式系统。我们感兴趣的是不可能结果的证明，这些结果通常使用关于收敛的非正式论点。首先，为了正确定义TVG序列的收敛，我们给出了TVG序列之间的距离。接下来，我们给出了一个通用的框架，它形式化地证明了任意确定性算法在任意收敛序列的TVG上的执行序列的收敛。最后，我们通过证明不存在确定性算法来计算任何随时间连通的TVG，即最弱类长寿命TVG的任何TVG，来说明上述结果的相关性。
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.