Reliability of augmented tree networks under pin-out constraints

The binary tree network provides a cost-efficient topology for parallel computers. However, its poor reliability makes it unattractive for applications that demand high reliability. This has motivated consideration of several augmented tree networks, but these networks offer increased reliability at the expense of increased node fanout. This paper studies 2 augmented tree networks that achieve high reliability with low node fanout. Exact reliabilities of both networks are computed in O(log(number of leaves)) time by deriving a system of recurrences that exploit their recursive construction. These structures are considerably more reliable than the single tree. Moreover, reliability is sensitive to the actual inter-leaf augmentation scheme-even a minor change has a noticeable impact on reliability. Two other measures of reliability, mean time-to-failure and mission time are estimated. A closed-form approximate expression for reliability of one of these networks is obtained; it agrees quite well with the exact value