Reconfigurability and reliability of systolic/wavefront arrays

Fault-tolerant redundant structures for maintaining reliable arrays are studied. It is assumed that the desired array (application graphic) is embedded in a certain class of regular, bounded-degree graphs called dynamic graphs. The authors define the degree of reconfigurability (DR), and DR with distance DR^d of a redundant graph. When DR (respectively DR^d) is independent of the size of the application graph, it is said that the graph is finitely reconfigurable, FR (resp. locally reconfigurable, LR). It is shown that DR provides a natural lower bound on the time complexity of any distributed reconfiguration algorithm, and that there is no difference between being FR and LR on dynamic graphs. It is then shown that if one wishes to maintain both local reconfigurability and a fixed level of reliability, a dynamic graph must be of dimension at least one greater than the application graph.