Faulty random geometric networks

被引:0
|
作者
Diaz, J. [1 ]
Petit, J. [1 ]
Serna, M. [1 ]
机构
[1] Dept. de Llenguatges, Univ. Politecnica de Catalunya, Campus Nord C6, Jordi Girona 1-3, 08034 Barcelona, Catalonia, Spain
关键词
Computational methods - Data communication systems - Distributed computer systems - Fault tolerant computer systems - Graph theory - Network protocols - Probability - Random processes;
D O I
10.1142/s0129626400000329
中图分类号
学科分类号
摘要
In this paper we analyze the computational power of random geometric networks in the presence of random (edge or node) faults considering several important network parameters. We first analyze how to emulate an original random geometric network G on a faulty network F. Our results state that, under the presence of some natural assumptions, random geometric networks can tolerate a constant node failure probability with a constant slowdown. In the case of constant edge failure probability the slowdown is an arbitrarily small constant times the logarithm of the graph order. Then we consider several network measures, stated as linear layout problems (Bisection, Minimum Linear Arrangement and Minimum Cut Width). Our results show that random geometric networks can tolerate a constant edge (or node) failure probability while maintaining the order of magnitude of the measures considered here. Finally we show that, with high probability, random geometric networks with (edge or node) faults do have a Hamiltonian cycle, provided the failure probability is constant. Such capability enables performing distributed computations based on end-to-end communication protocols.
引用
收藏
页码:343 / 357
相关论文
empty
未找到相关数据