Switching-Algebraic Evaluation of All-Terminal Reliability of a Computer-Communications Network: A Karnaugh-Map Perspective
Sultan Sameer Zagzoog *
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80200, Jeddah 21589, Saudi Arabia.
Muhammad Ali Rushdi
Department of Biomedical and Systems Engineering, Faculty of Engineering, Cairo University, Giza 12613, Arab Republic of Egypt and School of Information Technology, New Giza University, Giza 12256, Arab Republic of Egypt.
Emad Farah Khalaf
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80200, Jeddah 21589, Saudi Arabia.
Ali Muhammad Rushdi
Department of Electrical and Computer Engineering, King Abdulaziz University, P. O. Box 80200, Jeddah 21589, Saudi Arabia.
*Author to whom correspondence should be addressed.
Abstract
Network reliability is a fundamental measure for assessing the ability of a network to maintain successful connectivity under component failures. In computer-communications networks, reliability evaluation depends on whether all nodes remain mutually connected despite edge failures. This paper presents a Boolean-based framework for evaluating the all-terminal reliability of bidirectional networks. Network success and failure are formulated as coherent switching functions of independent edge success indicators, and their probabilistic expectations are obtained through the Probability Transform after deriving probability-ready expressions. The proposed approach integrates path-set, spanning-tree, and cut-set methods within a unified switching-algebraic setting. The all-terminal success is expressed as the conjunction of selected two-terminal successes and, equivalently, as a disjunction of spanning trees, whereas the all-terminal failure is represented through a disjunction of vertex cut-sets. Regular Karnaugh maps are used to visualise coherence, absorption, complementation, prime implicants, and disjointness, while variable-entered Karnaugh maps are used to provide compact factored representations that preserve statistical independence and facilitate the derivation of probability-ready expressions. The methodology is demonstrated for a running example of a five-node, seven-edge network. For this example, the all-terminal success function comprises 21 spanning trees and is shellable, whereas the complementary failure function comprises only 10 vertex cut-sets and is non-shellable. The case of components with equal reliabilities is further examined through the derivation of reliability and unreliability polynomials, comparison with related k-out-of-n systems, and identification of the lower boundary of useful redundancy. The results indicate that Boolean algebra and Karnaugh-map techniques provide a transparent, pedagogical, and effective approach for network reliability computation and visualization.
Keywords: All-terminal reliability, Boolean switching algebra, computer-communications networks, Karnaugh maps, probability-ready expressions, path sets, spanning trees, cut sets, vertex cut sets, shellability