Fault-tolerance of complete Josephus Cubes

The Complete Josephus Cube is proposed as a fault-tolerant node cluster architecture A reliable and cost-effective communications strategy is also presented. For a Complete Josephus Cube of dimension r, the strategy tolerates up to (r + 1) encountered faults in its routes that are deadlock-free and livelock-free. The message is optimally (respectively, sub-optimally) delivered in at most r (respectively, 2r + 1) hops. Message overhead is one of the lowest reported for the specified fault tolerance-with only a single (r + 2)-bit routing vector accompanying the message to be communicated. Associated routing hardware may be implemented with standard logic. (C) 2003 Elsevier B.V. All rights reserved.