Fast-Fault-Tolerant Parallel Communication and On-Line Maintenance Using Information Dispersal.
Journal
Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA '90, Island of Crete, Greece, July 2-6, 1990
Pages
378-387
Date Issued
1990
Author(s)
Abstract
Space-efficient Information Dispersal Algorithm (IDA) [11] is applied to parallel communication in the hypercube. Let N denote the size of the network. Our communication scheme runs in 2·log N + 1 time using constant size buffers. Its probability of successful routing is at least 1 - N-2.419·log N+1.5, proving Rabin's conjecture. The same scheme also tolerates O(N) random link failures with high probability. The scheme runs within the said time bound without long delay. On-line and efficient wire testing and replacement on the hypercube can be realized if our fault-tolerant routing scheme is used. Let α denote the total number of links in the hypercube. It is shown that ≈ α/352 wires can be disabled simultaneously without disrupting the ongoing computation or degrading the routing performance much.
SDGs
Type
conference paper