Diversity and Multi-Version Systems - Nuclear Power Plant Instrumentation and Control Systems for Safety and Security - page 195

between corresponding elements of FPGA- and
microcontroller-based technologies in printed
circuits board development technologies and
manufacturers.
These dependencies, therefore, essentially
complicate the task of the diversity type selection,
and leads to the necessity of developing a model
that allows for systematization of generation and
choice of diversity type pairs.
Diversity model and algorithm: The model
takes dependencies among diversity types into a
consideration and simplifies the choice of diver-
sity options.
A direct acyclic graph is used to represent the
proposed model. Each node of this graph corre-
sponds to some diversity type. Typically, several
nodes are used for one diversity type to reflect
dependencies. The edges are annotated (labeled)
with sets of possible design decisions (values of
diversity types). The order of nodes can be arbi-
trary. A path through the graph represents a set of
feasible diversity decisions, which are indepen-
dent within a given set. For each set, the possible
diversity values are restricted according to labels
of ongoing edges of the path through the graph,
but these values have no dependencies inside the
set and can be used in any combinations.
Based on diversity types presented in Table 4,
an example of the diversity model is developed
using abstract sets of diversity values. This makes
the example more general and applicable for vari-
ous types of computer systems. We consider seven
diversity types (Table 4) and seven dependencies
among the values of these types (Table 5), which
are typical for many safety-critical systems.
Each dependency in Table 5 shows feasible
combinations of diversity values. For example,
dependency 1 means that if one of the values—
TC1, TC2, or TC3—is chosen for diversity type
TC, then only the values—MC1, MC2, or MC3—
can be chosen for diversity type MC. Conversely,
if diversity values TC4, TC5, or TC6 are being
used, then only MC4 or MC5 can be used for MC.

For developing a diversity model, a subgraph
splitting algorithm is used, which has previ-
ously been developed for software test generation
(Vilkomir, 2009, Vilkomir, et al., 2009). In this
section, the algorithm is adapted for a new task of
a diversity model creation, and the meanings of
nodes and edges are completely different, when
compared with what was used for software test
generation models. However, the algorithm used
for model development here remains unchanged
from earlier research.
The algorithm starts from a linear direct graph,
which describes possible diversity values, but does
not reflect any dependencies between these values.
The graph is then modified by applying the algo-
rithm in a cycle for each dependency. Each cycle
includes four steps: splitting a subgraph, labeling
ingoing and outgoing edges of split subgraphs,
eliminating dead nodes and edges, and merging
nodes. Developing a diversity model for diversity
values from Table 4 with dependencies from Table
5 is considered below.
Developing a diversity model: Figure 8 repre-
sents different types of diversity (nodes) and sets
of their possible values (ingoing edges). To design
one subsystem (version) of a multi-version system,
it is necessary to choose a specific value from each
set. If there are no dependencies among diversity
types, any combination of values is possible.
Because of dependencies, some combinations
of diversity values are infeasible. To reflect de-

Table 4. Diversity types

Diversity Type Diversity Values

TC TC1, TC2, TC3, TC4, TC5,

TC6

MC MC1, MC2, MC3, MC4, MC5

FC FC1, FC2, FC3, FC4, FC5, FC6

TP TP1, TP2, TP3, TP4, TP5

MP MP1, MP2, MP3, MP4

L L1, L2, L3, L4, L5

TO TO1, TO2, TO3