Fault-tolerant multiple bus networks for fan-in algorithms

摘要

We consider a large class of algorithms called "fan-in algorithms" that are useful for problems involving semi-group operations. This paper deals with the design of fault-tolerant multiple bus networks (MBNs) suited to run fan-in algorithms. We present two methods for constructing fan-in MBNs with tolerance to bus faults, that have nearly optimal performance and processor fan-out. We also present a general framework that converts any fan-in MBN (including those resilient to bus faults) into one with tolerance to processor faults, and for which faulty processors slow the original algorithm (for fault-free processors) by only one step.