A fault-tolerant distributed subcube management scheme for hypercube multicomputer systems

This paper proposes a fault-tolerant distributed subcube management scheme for hypercube multicomputer systems. Gracefully degradable subcube management is supported by a data structure, called the distributed subcube table (DST), and a fault-tolerant broadcast protocol, called the reliably synchronized broadcast (RSB). In an n-dimensional hypercube, DST is the collection of 2ⁿ local subcube tables (LSTs), DST={LST₀, LST, ..., LST_2-1 ⁿ}, where LST, is a bit-mapped table assigned to N_x, a fault-free node whose address is x. LST_x, ∀_x, is n+1 bits long, and it records the status (free/busy) of certain subcubes adjacent to N_x. The RSB diagnoses and avoids faults during interprocessor communication to prevent faulty nodes from being allocated for job execution. In addition to possessing a fault-tolerant design, our scheme can also achieve comparable or better performance than existing centralized schemes, as verified by extensive simulation