A bubblesort network consists of nodes labeled with permutations of characters, so that two nodes have a direct connection when their corresponding permutations differ by the interchange of two adjacent characters. A multiprocessor system might be designed following this graph approach. This paper investigates how the reliability of such a network depends on the reliability of its nodes.
The paper provides theorems on the outlined constructions and analyzes some cases using graph theory. Next is a numerical analysis and simulation of the proposed solution. The basic formal results of the paper are that the theorems and lemmas provide an upper and lower bound for reliability in the context of a given parameter set for a multiprocessor architecture.
The numerical analysis and the diagrams presented show that the upper and lower bound via the simulation and numerical calculation are close to each other. The conclusion of the paper claims that this fact proves that the proposed approach is a good approximation. Nevertheless, the paper lacks empirical measurements or references to them.
The paper contains serious mathematics; to understand the basic ideas, the reader needs a profound knowledge that is grounded in graph theory, probability theory, and discrete mathematics.
The paper may be interesting for researchers in theoretical computer science, applied mathematics, and graph theory in IT. The measurements could be used in engineering networks consisting of computational units (either processors or servers), and may give IT researchers the opportunity to examine the validity of the theoretical results in an operational environment.