A Combinatorial Analysis of Distance Reliability in Star Network

This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) between the source node u and the destination node I with the shortest distance, in an n-dimensional star network, S_n. The shortest distance restriction guarantees the optimal communication delay between processors and high link/node utilization across the network. This paper uses a combinatorial approach by limiting the number of node, link and node/link failures. For each failure model, two different cases depending on the relative positions of u and I, are analyzed to compute DR. Furthermore, DR for the antipodal communication, where every node must communicate with its antipode, is investigated as a special case. For this case, lower bound on DR of those disjoint paths is also derived.