Fault-tolerant computing on trees

The paper analyzes the fault-tolerance of complete binary tree networks. It shows how an N-mode tree subject to random failures can simulate a perfect, fault-free tree under different fault models. If edges fail with independent probability p<¹ /₃ it shows both a lower bound and an approximately tight upper bound on the time required to simulate a perfect tree on the faulty tree. If edges are assumed to be robust and the nodes have a failure probability of p<¹/₂, then the faulty tree can simulate the fault-free tree with O(loglogN) slowdown. The paper also shows a matching lower bound for using all non-faulty processors. These results are combined to analyse other fault models. All the results hold with high probability