✦ LIBER ✦

Sparse networks tolerating random faults

✍ Scribed by T. Yamada; K. Nomura; S. Ueno

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 350 KB
Volume: 137
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00263-4

No coin nor oath required. For personal study only.

✦ Synopsis

A network G * is called random-fault-tolerant (RFT) network for a network G if G * contains a fault-free isomorphic copy of G with high probability even if each processor fails independently with constant probability. This paper proposes a general method to construct an RFT network G * for any network G with N processors such that G * has O(N ) processors. Based on the construction, we also show that if G is a Cayley, de Bruijn, shu e-exchange, or partial k-tree network with N processors and M communication links then we can construct an RFT network for G with O(N ) processors and O(M log N ) communication links. Cayley networks contain many popular networks such as circulant, hypercube, CCC, wrapped butter y, star, and pancake networks.

📜 SIMILAR VOLUMES

Finding a target subnetwork in sparse ne

Finding a target subnetwork in sparse networks with random faults

✍ Pierre Fraigniaud; Claire Kenyon; Andrzej Pelc 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 577 KB

The dynamics of sparse random networks

✍ Ali A. Minai; William B. Levy 📂 Article 📅 1993 🏛 Springer-Verlag 🌐 English ⚖ 1004 KB

Recurrent neural networks with full symmetric connectivity have been extensively studied as associative memories and pattern recognition devices. However, there is considerable evidence that sparse, asymmetrically connected, mainly excitatory networks with broadly directed inhibition are more consis

Fault-tolerant minimum broadcast network

Fault-tolerant minimum broadcast networks

✍ Ahlswede, R.; Gargano, L.; Haroutunian, H. S.; Khachatrian, L. H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 978 KB

Broadcasting is the task of transmitting a message originated at one processor of a communication network to all other processors in the network. A minimal k-fault-tolerant broadcast network is a communication network on n vertices in which any processor can broadcast in spite of up to k line failur

Fault-Tolerant Broadcasting in Radio Net

Fault-Tolerant Broadcasting in Radio Networks

✍ Evangelos Kranakis; Danny Krizanc; Andrzej Pelc 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 151 KB

We consider broadcasting in radio networks that are subject to permanent node failures of unknown location. Nodes are spread in a region in some regular way. We consider two cases: nodes are either situated at integer points of a line or they are situated in the plane, at grid points of a square or

A Fault-Tolerant Multistage Combining Ne

A Fault-Tolerant Multistage Combining Network

✍ Neng-Pin Lu; Chung-Ping Chung 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 379 KB

In this paper, we propose a solution to both fault tolerance and hot-spot contention problems in multiprocessor systems with multistage interconnection networks. Combining networks are known to be effective in handling hot-spot traffic. However, the fault tolerance capability of unique-path combinin

Networked control systems tolerant to fa

Networked control systems tolerant to faults

✍ Alessandro Casavola; Chandrasekhar Kambhampati 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 42 KB 👁 2 views