INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL

ISSN 1841-9836, 13(5), 772-791, October 2018.

How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks?

V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

Vlad Dr goi*

1. Faculty of Exact Sciences
Aurel Vlaicu University of Arad
Elena Dragoi St., 310330, Arad, Romania
2. Laboratoire LITIS - EA 4108
Université de ROUEN - UFR Sciences et Techniques
Avenue de l'université, 76800 Saint Etienne du Rouvray, France
*Corresponding author: vlad.dragoi@uav.ro

Simon R. Cowell, Valeriu Beiu, Sorin Hoar , P storel Ga³par

Faculty of Exact Sciences
Aurel Vlaicu University of Arad
Elena Dragoi St., 310330, Arad, Romania
{simon.cowell, valeriu.beiu, sorin.hoara, pastorel.gaspar}@uav.ro

Abstract: A classical problem in computer/network reliability is that of identi-
fying simple, regular and repetitive building blocks (motifs) which yield reliability
enhancements at the system-level. Over time, this apparently simple problem has
been addressed by various increasingly complex methods. The earliest and simplest
solutions are series and parallel structures. These were followed by majority voting
and related schemes. For the most recent solutions, which are also the most involved
(e.g., those based on Harary and circulant graphs), optimal reliability has been proven
under particular conditions.
Here, we propose an alternate approach for designing reliable systems as repetitive
compositions of the simplest possible structures. More precisely, our two motifs (basic
building blocks) are: two devices in series, and two devices in parallel. Therefore,
for a given number of devices (which is a power of two) we build all the possible
compositions of series and parallel networks of two devices. For all of the resulting two-
terminal networks, we compute exactly the reliability polynomials, and then compare
them with those of size-equivalent hammock networks.
The results show that compositions of the two simplest motifs are not able to surpass
size-equivalent hammock networks in terms of reliability. Still, the algorithm for com-
puting the reliability polynomials of such compositions is linear (extremely e�cient),
as opposed to the one for the size-equivalent hammock networks, which is exponen-
tial. Interestingly, a few of the compositions come extremely close to size-equivalent
hammock networks with respect to reliability, while having fewer wires.a

Keywords: two-terminal network, series and parallel network, composition, reliabil-
ity polynomial.

aThis paper is partially reprinted and extended, with permission based on Licence Number
4395350722700 © IEEE, from "2018 7th International Conference on Computers Commu-
nications and Control (ICCCC)."

1 Introduction

One well-known problem in information processing is that of identifying schemes (for a partic-
ular given technology) that maximize reliability. Reliability is an attribute of a system, a reliable
system being one which works error-free for extended periods of time�originally an issue only

Copyright ©2018 CC BY-NC



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 773

for safety-critical applications. The most common interpretation of network reliability [3], [4], [5]
is connectivity-based. In [5], the author emphasizes a variety of interpretations for the reliability
of networks, such as all-terminal, k-terminal or two-terminal networks:

�It comes as no surprise that hundreds of seemingly natural de�nitions arise by ex-
amining the plethora of di�erent types of networks, causes and types of failures, and
levels and types of operation. One should not expect to �nd a single de�nition for
reliability that accommodates the many real situations of importance.�

(Charles J. Colbourn)

Obviously, the design-for-reliability problem becomes more challenging as the system grows
larger (more complex) and is required to function without interruptions for longer times. Another
aspect of interest is that enhancing/maximizing reliability should be done with a limited number
of additional (redundant) components. The number of components is the simplest and most
obvious cost function, but other cost functions (also known as �gures-of-merit, or FoM) have
been proposed and used, such as, e.g., area, power, or energy. It follows that design-for-reliability
is a constraint optimization problem: maximize system reliability given limited resources (keeping
costs as small as possible). This problem permeates way beyond computers into most man-made
systems. Nature also seems to rely on reliability principles/schemes at di�erent levels (the most
well-known example here being the human brain, having 1011 neurons interconnected by 1015

axons and dendrites, working over many years).
In the following we shall �rst of all restrict the scope of our discussions to computers. In this

context, reliability was established through �ve lectures given at Caltech by John von Neumann
in January 1952, which were published four years later [22]. The focus was on how to design
reliable circuits/computers using unreliable logic gates. The answer was to replicate gates and
combine their e�ects by voting and/or multiplexing. Another take on this topic was advanced
four years later by Edward F. Moore and Claude E. Shannon [20], [21]. The major di�erence
was that instead of starting from gates, Moore and Shannon decided to pursue their analysis
starting from relays (switching devices). Their results were much more encouraging than [22].
In particular, their device-level scheme:

� can be used with arbitrarily poor devices (i.e., absolutely random switching devices);

� requires redundancy factors which are 10(2...3) (2 to 3 orders of magnitude) less than those
needed by gate-level schemes.

Clearly, logic gates are made out of switching devices (transistors), hence device-level ap-
proaches, such as [20] should be used to enhance the reliability of the gates, before applying
gate-level schemes such as those suggested in [22]. Still, this approach was not taken, as over the
last few decades, the CMOS transistors have always been reliable enough. With novel nanoscale
switching devices and nanoarchitectures under investigation [23], [26] the story is starting to look
di�erent [14], [13]. This prospect has triggered our interest in revisiting the work of Moore and
Shannon [7]. Their scheme for improving on an unreliable switching device was to replace the
device itself by a two-terminal network of identical unreliable switching devices.

That is why we further narrow down the focus of this paper to two-terminal networks. In
particular, Moore and Shannon have introduced in [20] and argued in [21] for a particular type
of two-terminal networks: hammock networks. A thorough comparison of hammock networks
with other highly e�ective specialized networks is called for. For instance, a comparison of
hammocks with circulant and Harary graphs (for which optimal reliability has been proven
under particular conditions [19], [9], [25]). In any case, regular networks bode well with novel



774 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

array-based designs including vertical FET, FinFETs [12], gate-all-around FET, and arrays of
beyond CMOS devices [6]. Our fresh analyses of small hammock networks [7] (as well as possible
extensions [8], [2]) are exact. They have con�rmed once again how challenging is to compute
the associated reliability polynomials. These suggest that the design-for-reliability process using
hammock networks will turn out to be quite involved.

An alternate design option (also mentioned in [20]) advocates for growing larger networks by
combining two smaller networks. These can be connected in series, in parallel, or by "composing"
them, i.e., replacing each and every element of a network with the other network (translates
into composing their associated reliability polynomials). Compositions of hammock networks
are mentioned in [20] and [21]. Still, series and parallel networks are easier to evaluate (as
their reliability polynomials are simpler [17]), while compositions of series and parallel networks
inherit this bene�t. It means that one clear advantage of an approach that relies on composing
series and parallel networks is a simpler design procedure. The fundamental question is how such
composed networks perform versus other two-terminal networks of the same size. In particular,
in this paper we compare compositions of small series and parallel networks versus hammock
networks.

Related work. First of all we mention that this article is an extended version of a conference
paper [10]. We bring here new results concerning combinatorial properties of compositions and
a more detailed analysis of the various FoMs as functions of some speci�c design requirement,
such as number-of-devices and wires. The same technique of composing networks was also used
in [1]. There the authors compared hammock networks with compositions of smaller hammock
networks. Their results emphasize the merit of composing smaller networks, as they come re-
ally close to hammocks while having more e�cient algorithms for computing their reliability
polynomials.

Our contribution. The main results that we prove in this article can be summarized as
follows:

� Compositions of series and parallel networks are planar matchstick minimal networks (see
Proposition 4);

� Their width w and length l, as well as number-of-devices n and wires ω are related to the
Hamming weight of the corresponding binary vector (see Proposition 5 and Theorem 11);

� There is an algorithm that determines whether a matchstick minimal network is a com-
position of series and parallel. Our solution is a symmetric binary tree decomposition of
depth m = log2 n;

� The reliability polynomial of compositions of series and parallel networks can be computed
very e�ciently (see Theorem 16).

The article also provides essential simulations, by detailing the reliability polynomials for all
compositions of series and parallel networks with n = 64 as well as for the two 8-by-8 hammocks.
By means of several FoMs we give arguments which prove that, in this particular case, hammocks
are more reliable than compositions of series and parallel networks. However, the advantage of
compositions is undeniable since they come close to hammocks, they have fewer wires for the
same number of devices, and more signi�cantly in our opinion, their reliability can be computed
e�ciently.

Organisation of the paper. The paper is structured as follows. We introduce two-terminal
and hammock networks in Section 2. Compositions of series and parallel networks are discussed
in Section 3. Section 4 starts by introducing reliability polynomials and several FoMs that we are
going to use. Afterwards, we determine (exactly) the reliability polynomials for the hammock



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 775

and composition networks under investigation, and use these for comparative analyses. The
paper ends with some conclusions and further directions for research.

2 Two-terminal networks

2.1 De�nitions and properties

De�nition 1. Let n be a strictly positive integer. We say that N is a two-terminal network of
size n, or an n-network if N is a circuit, made of n identical devices, that has two distinguished
contacts/terminals: an input or source S, and an output or terminus T .

With any two-terminal network we associate three parameters: width w, length l, and size
n. The width w of N is the size of a �minimal cut" separating S from T . The length l of N is
the size of a �minimal path" from S to T . The size of a two-terminal network N is related to l
and w by:

n ≥ wl (1)

(see Theorem 3 in [20]).
When the equality in eq. (1) holds, we say that N is a minimal network. Even though there

are several types of minimal networks, we will study here only matchstick minimal networks N.
We will denote a matchstick minimal network of width w and length l by Nw,l. The set of all
matchstick minimal networks of size n = wl will be denoted Nn, and we have:

N =
⋃
n

Nn and Nn =
⋃
w|n

Nw,n/w. (2)

Notice that the set N1,1 has cardinality 1, since there is only one two-terminal network with
w = l = 1, that is the single device network N1,1. In the sequel, we will distinguish two subsets
of Nn, namely the set of hammocks and the set of compositions of series and parallel networks.

2.2 Hammock networks

Matchstick minimal networks with the well-known �brick-wall� pattern are known as ham-
mocks [20] (see Fig. 1). They can be generated starting from a parallel-of-series PoS network(see
Fig. 1) by connecting vertically adjacent pairs of wires by short vertical �matchsticks� (red ver-
tical lines in Fig. 1). If w and l are both even there are two solutions Hw,l and H

+
w,l (see Fig.

1), while otherwise we are left only with Hw,l (see [7] for more details).

S T

p p p p

p p p p

p p p p

p p p p

4-by-4 PoS

S T

p p p p

p p p p

p p p p

p p p p

H4,4

S T

p p p p

p p p p

p p p p

p p p p

H+4,4

S T

p p p p

p p p p

p p p p

p p p p

4-by-4 SoP

Figure 1: Square 4-by-4 parallel-of-series, hammocks and series-of-parallel.



776 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

3 Compositions of series and parallel

3.1 De�nitions and properties

De�nition 2. Let C represent a composition of networks. If we start from the device itself the
simplest possible compositions are: two devices in series C(0), and two devices in parallel C(1).
At the to the next level, a composition of C(0) with C(1) is C = C(0) • C(1) which is obtained
by replacing each device in C(0) by C(1), with the convention that the nodes S and T in C(1)

where unlabeled. This composition will be abbreviated as Cu, where u = (0, 1).

Notation 3. More generally, given u = (u0, . . . ,um−1) ∈ {0, 1}m, we will denote by Cu the
composition C(u0) •· · ·•C(um−1), and the set of all such compositions by C2m (as an example see
C23 in Fig. 2).

S Tpp pp pp pp

C(0,0,0)

S T
p p p p

p p p p

C(1,0,0)

S T
p p p p

p p p p

C(0,1,0)

S T
p p p p

p p p p

C(0,0,1)

S T

p p

p p

p p

p p

C(1,1,0)

S T

p p

p p

p p

p p

C(1,0,1)

S T

p p

p p

p p

p p

C(0,1,1)

S T

p

p

p

p

p

p

p

p

C(1,1,1)

Figure 2: All the elements of the set C23.

Theorem 4. Let m be a strictly positive integer. Then any element in C2m is a matchstick
minimal network of size 2m. Moreover, we have #C2m = 2m.

Proof: The fact that compositions of C(0) and C(1) are matchstick minimal networks follows
from Theorem 3 in [20]. The set of compositions of C(0) and C(1) is:

C2m = {Cu|u ∈{0, 1}m}, (3)

from which it follows immediately that #C2m = 2m. 2

Notice that Proposition 4 provides an e�cient method for generating matchstick minimal
networks of size n = 2m. Further we will detail how to compute w and l for any network
C ∈ C2m. To achieve this goal, we introduce the well-known concept of Hamming weight from
coding theory. For any binary vector u ∈ {0, 1}m, its Hamming weight |u| is the number of
non-zero components of u.

Theorem 5. Let m be a strictly positive integer and Cu ∈ C2m. Then Cu is a matchstick
minimal network of size 2m, length l = 2m−|u| and width w = 2|u|.



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 777

Proof: For a binary m-tuple u = (u0, . . . ,um−1) ∈ {0, 1}m the weight |u| gives the number
of times C(1) is present in the composition, i.e., the number of times we compose in parallel.
By induction it can be deduced that w = 2|u|. Since Cu has n = 2m devices, it follows that
l = 2m−|u|. 2

In conclusion, writing

C2i,2m−i =
{
C2|u|,2m−|u||u ∈{0, 1}

m,|u| = i
}

(4)

we have

C2m =
m⋃
i=0

C2i,2m−i (5)

3.2 Combinatorial properties

Since compositions of C(0) and C(1) o�er an e�cient way of creating matchstick minimal
networks, the �rst question that we raise here is to determine the proportion of compositions.
In other words, if one randomly picks a matchstick minimal network N ∈ N2m ,with respect
to the uniform distribution over the set of all matchstick minimal networks, then �What is the
probability that N ∈C2m?�

Theorem 6. Let N be a matchstick minimal network of size 2m. Then we have

Pr(N ∈C2m) ∼ 2−(2
bm/2c−1)(2dm/2e−1)+m.

Proof: From [7] we have that for a �xed l and w such that n = wl the number of match-
stick minimal networks of length l and width w equals 2(l−1)(w−1). Hence the total number of
matchstick minimal networks of size 2m is equal to

m∑
i=0

2(2
i−1)(2m−i−1) ∼ 2(2

bm/2c−1)(2dm/2e−1), (6)

which ends our proof. 2

So, if we randomly pick a matchstick minimal network N, the probability that N is a
composition of C(0) and C(1) is rapidly decreasing while m is increasing. However, the question
now is how to determine whether N is an element of C2m. To answer this question we de�ne the
following two operations

De�nition 7 (Vertical/horizontal cut). Let n,w,l be strictly positive integers and N be a
matchstick minimal network of width w and length l. We say that N admits a vertical cut
if there exists a vertical complete matchstick, and we write N = (Nl|Nr). We say that N
admits a horizontal cut if there is a horizontal free band, i.e. with no matchsticks,and we write

N =

(
Nu
Nd

)
.

Lemma 8. Let w and l be strictly positive integers and N be a wl matchstick minimal network.
Then N can not admit both a horizontal and a vertical cut.

Proof: The result is straightforward from the de�nition of a horizontal and vertical cuts (De�-
nition 7). 2



778 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

S T

p p p p

p p p p

p p p p

p p p p

N =

(
Nu
Nd

)
S T

S T

p p p p

p p p p

p p p p

p p p p

Nu and Nd
(a)

S T

p p p p

p p p p

p p p p

p p p p

N = (Nl|Nr)

S T S T

p p p p

p p p p

p p p p

p p p p

Nl Nr
(b)

Figure 3: Matchstick minimal networks that admit: (a) horizontal cut; (b) vertical cut.

In this article we only consider those vertical and horizontal cuts that bisect the network into
two identical halves. In other words a wl -network N can be cut vertically or horizontally and

we write N = (Nl|Nr) with Nr = Nl, or N =
(
Nu
Nd

)
with Nu = Nd, where Nl is a w × l/2

network and Nu is a w/2 × l network.

Theorem 9 (Decomposable networks). Let m be a strictly positive integer and N be a matchstick
minimal network of size n = 2m.

� if N = (Nl|Nl) (i.e., admits a vertical cut in half), then N = C(0) •Nl;

� if N =

(
Nu
Nu

)
(i.e., admits a horizontal cut in half), then N = C(1) •Nu.

Moreover, N ∈C2m if and only if N admits a binary tree decomposition, with respect to �|�
and �−�, of depth m, where the leaves of the tree are N1,1.

The proof of this proposition is based on the previous Lemma.

Remark 10. Notice that Hw,l is not decomposable as a compositions of C
(0) and C(1) unless

w = 1, l = 1, or w = l = 2, as it does not admit either a vertical or horizontal cut.

Algorithm 1 Decomposition of matchstick minimal networks into composition of C(0) and C(1)

Input:A matchstick minimal network N of size w × l = 2m
Output:The corresponding binary vector u if N is decomposable

1: u = [ ]
2: while N 6= N1,1 do
3: if N = (Nl|Nl) then
4: N = Nl
5: Append 0 to u

6: else if N =
(
Nu
Nu

)
then

7: N = Nu
8: Append 1 to u
9: else
10: Break;
11: end if
12: end while



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 779

3.3 Representations

In order to compare compositions with Hammocks we consider the parameters of the circuits,
that is the number of devices n, as well as the number of wires, ω in the circuits . The �rst
representation of the brick-wall pattern, which is from Moore and Shannon [20], uses vertical
matchsticks as in Fig. 1. The second possibility also suggested by Moore and Shannon [20] is to
use the graph representation. Here, we will adopt the third representation from [21], which gave
the name to these networks: hammocks. These three representations can all be seen in Fig. 4.

When counting the number of wires ω we will consider that there are w wires that connect S
to the circuit, and w wires that connect T to the circuit. We also count 4 wires whenever we have
an �X� shape matchstick. With this convention at hand we can now count ω for a matchstick
minimal network, in particular a composition or a hammock.

S T

p p p p

p p p p

p p p p

p p p p

Brick-wall representation ( [20])

S T

p p p p

p p p p

p p p p

p p p p

Hammock representation ( [21])

S T

Graph representation ( [20])

Figure 4: Three di�erent representations of H4,4.

Theorem 11. Let m be a strictly positive integer and Cu ∈ C2m. Then the number of wires
of the circuit Cu is ω = 2m + 2i+1, where i is the position of the most signi�cant bit of the
corresponding binary vector u equal to 1. When u is the zero vector the number of wires is
ω = 2m + 1.

Proof: The �rst case u = (0, . . . , 0) ∈ {0, 1}m can be easily deduced from the de�nition of the
composition. Next consider u = (1, 0, 0, . . . , 0) ∈ {0, 1}m. This circuit Cu is a parallel of two
identical circuits Cv where v = (0, . . . , 0) ∈ {0, 1}m−1. But we know that the number of wires
for Cv is ω = 2m−1 + 1 and the number of devices for Cv equals 2m−1. We also deduce that there
are 2m/2m−1 = 2 identical blocks in the composition of Cu. Notice that these two blocks do not
share any wire in common. Hence, we obtain the total number of wires for Cu, that equals the
number of blocks times the number of wires in each block. More exactly the number of wires for
Cu is ω = 2 ×

(
2m−1 + 1

)
= 2m + 2.

Now we can prove our theorem for any u ∈ {0, 1}m. Let u = (u0, . . . ,um−1) be a binary
vector such that ui = 1 and uj = 0 for any j > i. Denote ui,m−1 = (ui, . . . ,um−1) , which equals
ui,m−1 = (1, 0, . . . , 0). Notice that Cui,m−1 is composed of 2m−i devices and 2m−i + 2 wires. We
also know that there are 2m/2m−i identical blocks, all equal to Cui,m−1, that do not share any
wire in common such that Cu is the composition of these blocks. Then the number of wires of
Cu is ω = 2i ×

(
2m−i + 2

)
= 2m + 2i+1.

2

Theorem 12. Let w and l be two strictly positive integers. Then

ω =




2wl− l for Hw,l with w and l even
2wl− l + 1 for Hw,l with w or l odd
2wl− l + 2 for H+w,l with w and l even

(7)



780 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

Proof: We give here only the proof for one of the cases. For the remaining two cases the
arguments are exactly the same. So, let l and w be two odd strictly positive integers. This
implies that we have l− 1 columns of "X" shape matchsticks and horizontal wires. On each one
of these columns we count (w − 1)/2 matchsticks and one horizontal wire. Hence, each column
has 4×((w−1)/2) + 1 wires. And there are l−1 such columns, which makes the total number of
"interior" wires equal to (l− 1) × (2w− 1). By "interior" wire we mean wires that connect only
devices and not S or T with any of the devices. Finally, we have to add the number of "exterior"
wires, namely those connecting to S and T , which are 2w. Thus, we obtain ω = 2wl− l + 1. 2

Corollary 13. For square hammocks we obtain

ω =




8k2 − 2k for H2k,2k
8k2 − 2k + 2 for H+2k,2k
8k2 + 6k + 2 for H2k+1,2k+1

(8)

Remark 14. From eq. (8) taking k = 2m/2 it follows that H2m/2,2m/2 has 8×
(
2m/2−1

)2
−2m/2 =

2m+(2m−2m/2) wires. Also notice that from Theorem 11 there are
(
m
m/2

)
/2 elements in C2m/2,2m/2

having at most 2m + 2m−1 wires, which is smaller than 2m + (2m − 2m/2).

4 Evaluating reliability

4.1 Reliability polynomials

We will use a classical convention for the reliability polynomial R(p), where p ∈ [0, 1] is the
probability that a device is closed. Since the polynomial is associated with a network N (either
H or C), we shall use the notation R(N; p). This gives R(C; p) and R(H; p) for compositions
of C(0) and C(1) and respectively hammocks.

Lemma 15. R(C(0); p) = p2 and R(C(1); p) = 1 − (1 −p)2.

This is well-known [22], [20]. We can now determine the reliability R(C; p) for any C.

Theorem 16. Let m be a strictly positive integer and u = (u0, . . . ,um−1) ∈{0, 1}m. Then:

R(Cu; p) = R(C(u0)) ◦ · · · ◦R(C(um−1); p), (9)

where R(C(0); p) and R(C(1); p) are given by Lemma 15.

The proof of Theorem 16 follows directly from De�nition 2 and Lemma 15.

Remark 17. Notice that compositions of C(0) and C(1) are by de�nition series and parallel net-
works. Hence, they inherit all the nice properties of this big family of networks. Series and
parallel networks were extensively studied [24], [18], [11] and e�cient algorithms exist for com-
puting their reliability polynomials (the complexity of these algorithms is linear in n). However,
as we have shown in Theorem 16, compositions of C(0) and C(1) admit a closed form formula of
complexity log2(n) for computing their reliability polynomials.



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 781

Table 1: Reliability polynomials for Cu.

N R(N; p)

C(1,1,1,0,0,0) 8p8 − 28p16 + 56p24 − 70p32 + 56p40 − 28p48 + 8p56 −p64

C(1,1,0,1,0,0)
16p8 − 16p12 − 92p16 + 192p20 + 112p24 − 720p28 + 698p32 + 384p36
−1552p40 + 1744p44 − 1116p48 + 448p52 − 112p56 + 16p60 −p64

C(1,0,1,1,0,0)
32p8 − 96p12 − 120p16 + 1424p20 − 4424p24 + 8304p28 − 10894p32 + 10560p36

−7744p40 + 4320p44 − 1816p48 + 560p52 − 120p56 + 16p60 −p64

C(0,1,1,1,0,0)
64p8 − 448p12 + 1680p16 − 4256p20 + 7952p24 − 11424p28 + 12868p32 − 11440p36

+8008p40 − 4368p44 + 1820p48 − 560p52 + 120p56 − 16p60 + p64

C(1,1,0,0,1,0)

64p8 − 128p10 + 96p12 − 32p14 − 1532p16 + 6144p18 − 10752p20 + 10752p22 + 9664p24 − 95616p26
+269664p28 − 450464p30 + 441338p32 + 118784p34 − 1729536p36 + 4486144p38 − 7423040p40

+8938624p42 − 8199136p44 + 5857184p46 − 3294716p48 + 1464320p50−
512512p52 + 139776p54 − 29120p56 + 4480p58 − 480p60 + 32p62 −p64

C(1,0,1,0,1,0)

128p8 − 256p10 − 320p12 + 1472p14 − 5496p16 + 15616p18 + 7200p20 − 138656p22 + 254648p24 + 104576p26−
1062432p28 + 1528032p30 − 17422p32 − 3037184p34 + 4820608p36 − 3005056p38 − 1494624p40

+5473536p42 − 6668992p44 + 5345344p46 − 3166616p48 + 1441024p50
−509600p52 + 139552p54 − 29112p56 + 4480p58 − 480p60 + 32p62 −p64

C(0,1,1,0,1,0)

256p8 − 512p10 − 2688p12 + 9088p14 + 5904p16 − 61952p18 + 61632p20 + 165440p22 − 454320p24 + 141568p26
+1016256p28 − 1785920p30 + 443716p32 + 2654720p34 − 4588384p36 + 2904160p38 + 1526280p40

−5480576p42 + 6670048p44 − 5345440p46 + 3166620p48 − 1441024p50
+509600p52 − 139552p54 + 29112p56 − 4480p58 + 480p60 − 32p62 + p64

C(1,0,0,1,1,0)

512p8 − 3072p10 + 8960p12 − 16640p14 − 43744p16 + 765312p18 − 4637568p20 + 18013760p22 − 51204560p24
+113425312p26 − 203255568p28 + 301928416p30 − 378028286p32 + 403556352p34 − 370208768p36

+293307392p38 − 201225472p40 + 119608832p42 − 61506048p44 + 27263232p46 − 10354528p48
+3339648p50 − 903168p52 + 201152p54 − 35952p56 + 4960p58 − 496p60 + 32p62 −p64

1024p8 − 6144p10 + 1536p12 + 114176p14 − 542144p16 + 1039104p18 + 797952p20 − 11825024p22
C(0,1,0,1,1,0) +43312992p24 − 105270976p26 + 196334304p28 − 297069632p30 + 375202628p32 − 402199296p34

+369674944p36 − 293137856p38 + 201182992p40 − 119600736p42 + 61504944p44 − 27263136p46
+10354524p48 − 3339648p50 + 903168p52 − 201152p54 + 35952p56 − 4960p58 + 496p60 − 32p62 + p64

C(0,0,1,1,1,0)

4096p8 − 57344p10 + 415744p12 − 2050048p14 + 7653632p16 − 22887424p18 + 56715264p20
−119066112p22 + 214987136p24 − 337392384p26 + 463591296p28 − 560492800p30 + 598138512p32

−564338304p34 + 470897216p36 − 347203584p38 + 225750336p40 − 129016384p42
+64511136p44 − 28048704p46 + 10518296p48 − 3365856p50 + 906192p52 − 201376p54

+35960p56 − 4960p58 + 496p60 − 32p62 + p64



782 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

For hammocks we rely on the results just published in [7] as well on the ones for H8,8 and
H+8,8 recently reported in [10], [1]. The associated reliability polynomials were computed using
our own recursive depth-�rst traversal of a binary tree algorithm, and are reported in Table 2.

Table 2: Reliability polynomials for H+8,8 and H8,8.

N R(N; p)

H8,8

650p8 − 580p9 + 908p10 − 6880p11 + 4628p12 − 12104p13 + 31618p14 + 372p15 + 10594p16 + 196688p17 − 404536p18
+915388p19 − 5608084p20 + 7645892p21 − 12887466p22 + 56185408p23 − 61734474p24 + 83601572p25
−412397124p26 + 272424760p27 + 274694424p28 + 1746408000p29 − 221980272p30 − 12868843904p31

+11123958002p32 − 11120041788p33 + 156260690872p34 − 378857360436p35 + 264833158482p36
−60539595908p37 + 345161573768p38 + 1581294699620p39 − 10357633700988p40 + 19594821559752p41

−7205288635438p42 − 36413539831436p43 + 75842387925382p44 − 55098726855452p45 − 30641343744796p46
+111186328020944p47 − 111483252211446p48 + 33001245825824p49 + 53388841078258p50 − 85170175686428p51
+59759032847258p52 − 15870886733412p53 − 12944378218252p54 + 19685718553176p55 − 14268363534224p56

+7162471625508p57 − 2694331712884p58 + 775005119032p59 − 169487849178p60 + 27440435336p61
−3113881376p62 + 221751056p63 − 7474305p64

H+8,8

720p8 − 720p9 + 1052p10 − 7864p11 + 6482p12 − 16012p13 + 43042p14 − 16492p15 + 35378p16 + 202080p17 − 418416p18
+840000p19 − 6142350p20 + 7346188p21 − 11370674p22 + 74129792p23 − 100005860p24 + 118520824p25
−656753496p26 + 1014391664p27 − 1060302334p28 + 5318496368p29 − 8451329352p30 + 2451624096p31
−37298482094p32 + 119852403404p33 − 23621628548p34 − 197506250928p35 − 337635320852p36

+1438498163768p37 − 67797908976p38 − 4198255335740p39 + 3015682674902p40 + 8881103035456p41
−15082194064786p42 − 3506508481748p43 + 18452358491432p44 + 39640921395644p45 − 181496618059380p46

+286828005143040p47 − 191038611524520p48 − 138468526731136p49 + 542912067034010p50 − 803232038481876p51
+814719587176720p52 − 634769854840740p53 + 396340290321940p54 − 202017905414696p55 + 84634369170678p56

−29121695246028p57 + 8171460088944p58 − 1843848199008p59 + 327008804562p60 − 43949841128p61
+4211763728p62 − 256604464p63 + 7474305p64

4.2 Figures-of-merit

To compare compositions with hammocks we will rely on several FoMs:

1. The well-known Reliability Improvement Index (RII) introduced by Klaschka in [15], [16];

2. The steepness of R(N; p) mentioned by Moore and Shannon [20];

3. The variation of R(N; p), which was mentioned in [10].

Reliability Improvement Index

The Reliability Improvement Index is de�ned [15], [16] for any network N as

RII(N) =
log(p)

log (R(N; p))
. (10)

The RII is a measure of the reliability increase produced by a network N and was used in [7] to
estimate how much matchstick minimal networks improve on a single device.

Steepness of the reliability polynomials

The ideal reliability function proposed by Moore and Shannon is the staircase function:

χ(p) =

{
0 0 ≤ p ≤ 0.5
1 0.5 < p ≤ 1



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 783

One of the goal of [20] was to identify networks having reliability polynomials exhibiting steep
0 → 1 transitions. We de�ne FoM1 as:

FoM1 = max
p∈[0,1]

R′(N; p). (11)

Since the transition point might be important, we give a �ner FoM for the steepness of the
polynomials. This is an enhancement over FoM1 which measures how steep is the reliability
polynomial as well as how far from 0.5 is the threshold. So, in general FoM∗1 is equal to FoM1
weighted by a function of the distance between p0 and 0.5. Here, we choose a very simple function,
that is

FoM∗1 = max
p∈[0,1]

R′(N; p) ·
1

|0.5 −p0|
, (12)

where p0 is the point where the maximum is achieved. Notice that in our case this is well-de�ned
since no network studied in this paper has p0 = 0.5. But this is no longer the case for self-dual
networks where p0 = 0.5, and a modi�ed FoM1 should be proposed.

Variation of the reliability polynomial

Another FoM is introduced in this paper. It is related to the variation achieved by a reliability
polynomial in a given interval. We shall use the area under R′(N; p) in a given symmetric interval
(with respect to 0.5). This is exactly the variation of R(N; p) on that interval, hence for any N:

FoM2(p0) = R(N; 1 −p0) −R(N; p0) =
1−p0∫
p0

R′(N; p)dp. (13)

This FoM2 is well-de�ned for the staircase function since χ may be written as the integral of
the delta Dirac function over the sub-domain [0, 1]. Therefore, FoM2 is the area under the delta
Dirac function, between two symmetric points t and 1 − t, with 0 ≤ t < 0.5.

4.3 Numerical results

Reliability improvement index

The �rst set of simulations was performed over the whole set C26 as well as for the two
hammocks under investigations, H8,8 and H

+
8,8 (see Table 2). Using eq. (10) we have calculated

all the RIIs. These can be seen in Fig. 5,6,7. In Fig. 5 the scale is linear to get a clear picture
of the very large RII values for p close to 1. In includes only the square networks, more exactly
N ∈ C8,8 in blue and N = H8,8,H+8,8 in red. A zoom in on the region of interest is shown in
Fig. 6, where the yellow horizontal line at RII = 1 represents the border between networks that
improve reliability and networks which do not. Finally, the complete picture (Fig. 7), in log
scale, includes all networks N ∈C26, the non-square ones being plotted in orange.

This �gure shows a wide range of variation for RIIs. Among these, those which go below
RII = 1 are not improving over a single device, which means they should not be used. This is in
support of selecting square networks which tend to stick together close to RII = 1 when p = 0.5.



784 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

Figure 5: RII(N) for N ∈C8,8 (blue) and N = H8,8,H+8,8 (red).

Figure 6: Zoom on RII(N) for N ∈C8,8 (blue) and N = H8,8,H+8,8 (red).



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 785

Figure 7: RII(N) for N ∈C8,8 (blue), N = H8,8,H+8,8 (red) and N ∈C26 \C8,8 (orange) in log
scale.

Steepness of the reliability polynomials

In Fig. 8 we plot R′(N; p) for all N ∈ C8,8, as well as N = H8,8 and N = H+8,8. We
notice that max

p∈[0,1]
R′(H8,8; p) = max

p∈[0,1]
R′(H+8,8; p) = 3.75252 and is reached at p0 = 0.501745,

respectively p0 = 0.498255. For compositions we have:

max
C∈C8,8

(
max
p∈[0,1]

R′(C; p)

)
= 4.1035,

which is achieved by u = (1, 1, 1, 0, 0, 0) at p0 = 0.760.



786 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

Figure 8: R′(N; p)

This result shows the limitation of this FoM, as it does not take into account how far the
threshold point is from the desired point, that is 0.5. That is why the enhanced version of this
FoM, namely FoM∗1 gives better results in comparing reliability. This fact is illustrated in Fig.
9 and 10.

Figure 9:
R′(N; p)

|p0 − 0.5|



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 787

Figure 10: log
(
R′(N; p)

|p0 − 0.5|

)

We observe from Fig. 9 and 10 that hammocks are �better� than compositions with respect
to FoM∗1 . Indeed, for hammocks we obtain FoM

∗
1 (H8,8) = 1876.25 and for compositions we

have

max
C∈C8,8


 maxp∈[0,1] R′(C; p)

|p0 − 0.5|


 = 587.56,

which is achieved by u = (0, 1, 0, 1, 1, 0) and u = (1, 0, 1, 0, 0, 1).

Variation of the reliability polynomials

In Fig. 11 we plot R(N; 1−p0)−R(N; p0) as a function of 0 ≤ p0 < 0.5 for H8,8 and H+8,8,
and C ∈C8,8.

Figure 11: R(N; 1−p0)−R(N; p0) as a function of p0 (0 ≤ p0 < 0.5);N = H8,8 and H+8,8 (red),
N = C ∈C8,8 (blue), and χ(1 −p0) −χ(p0) (green).



788 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

We notice a di�erence between the curves starting to develop from p0 = 0.25 onwards. In
Table 3 we report the exact values for p0 = 0.25, which correspond to R(0.75) −R(0.25). The
two hammocks we have considered here achieve the same value R(H8,8; 0.75) −R(H8,8; 0.25) =
0.985173. For compositions the best value

max
u∈{0,1}6

R(Cu; 0.75) −R(Cu; 0.25) = 0.979507,

is achieved for u = (0, 1, 0, 1, 1, 0) and u = (1, 0, 1, 0, 0, 1). It should be mentioned that the same
two compositions achieve the best values for FoM∗1 . In fact, FoM2(0.25) correlates perfectly
with FoM∗1 . Indeed, if we totally order compositions and hammocks with respect to FoM

∗
1 , then

the same order holds for FoM2(0.25). And as expected, the two FoMs point out to the same
network as being the most reliable, namely the hammock.

Recall that one of the leading arguments when comparing networks was the restriction of
the number of devices, which in our case study is always n = 64. Now, if we plot FoM2(0.25)
as a function of the number of wires ω, we see that one of the best compositions, namely
u = (0, 1, 0, 1, 1, 0) has fewer wires than the hammocks (see Fig. 12).

Figure 12: R(N; 0.75) − R(N; 0.25) as a function of the number of wires ω. N = H8,8 and
N = H

+
8,8 (red), and N = C with C ∈C8,8 (blue)

Figure 13: Zoom on the values of R(N; 0.75)−R(N; 0.25) in the vicinity of the maximum values



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 789

Table 3: Figure-of-merit for C ∈C8,8, H8,8, and H+8,8.

ω N p0 max
p∈[0,1]

R′(N; p)

max
p∈[0,1]

R′(N; p)

|p0 − 0.5|
R(N; 0.75) −R(N; 0.25)

120 H8,8 0.498 3.7525 1876.25 0.985173

122 H+8,8 0.502 3.7525 1876.25 0.985173

72 C(1,1,1,0,0,0) 0.760 4.1035 15.78 0.569843

C(1,1,0,1,0,0) 0.710 3.9273 18.70 0.736601

80 C(1,0,1,1,0,0) 0.665 3.7709 22.85 0.848154

C(0,1,1,1,0,0) 0.626 3.5995 28.56 0.905953

96

C(1,1,0,0,1,0) 0.643 3.6861 25.77 0.891705

C(1,0,1,0,1,0) 0.596 3.6409 37.92 0.947539

C(0,1,1,0,1,0) 0.555 3.5568 64.66 0.968192

C(1,0,0,1,1,0) 0.536 3.5354 98.20 0.975413

C(0,1,0,1,1,0) 0.494 3.5254 587.56 0.979507

C(0,0,1,1,1,0) 0.445 3.4606 62.92 0.968192

128

C(1,1,0,0,0,1) 0.555 3.4606 62.92 0.968192

C(1,0,1,0,0,1) 0.506 3.5254 587.56 0.979507

C(0,1,1,0,0,1) 0.464 3.5354 98.20 0.975413

C(1,0,0,1,0,1) 0.445 3.5568 64.66 0.968192

C(0,1,0,1,0,1) 0.404 3.6409 37.92 0.947538

C(0,0,1,1,0,1) 0.357 3.6861 25.77 0.891705

C(1,0,0,0,1,1) 0.374 3.5995 28.56 0.905953

C(0,1,0,0,1,1) 0.335 3.7709 22.85 0.848154

C(0,0,1,0,1,1) 0.290 3.9273 18.70 0.736601

C(0,0,0,1,1,1) 0.240 4.1035 15.78 0.569843

Strong points of compositions

Notice that for u = (0, 1, 0, 1, 1, 0) the corresponding composition comes really close to H8,8
and has an advantage over H8,8, in that C(0,1,0,1,1,0) has only 96 wires, while H8,8 has 120. From
a computational point of view, R(Cu; p) has several advantages over R(H8,8; p).

� Firstly, notice that the order of magnitude of the largest coe�cient is 109 for Cu compared
with 1014 for H8,8.

� Secondly, the reliability polynomials for compositions are sparser than R(H8,8; p). This is
due to the fact that R(Cu; p) have non-zero coe�cients only for even powers of p, i.e., 29
non-zero coe�cients versus 57 for R(H8,8; p).

� Thirdly the absolute values of the coe�cients of R(H8,8; p) are larger on average than the
coe�cients of R(Cu; p). For the case m = 6, the average value of a coe�cient is of the
order 1.3 × 1013 for hammocks, compared with 8.6 × 107 for compositions.

From the computational point of view all these arguments favor compositions over hammocks.



790 V. Dr goi, S.R. Cowell, V. Beiu, S. Hoar , P. Ga³par

5 Conclusions

In this article we have proposed and analyzed two-terminal networks generated through the
repeated composition of the simplest series and parallel networks. We have detailed several
structural properties of such networks and have presented an e�cient method for computing
their associated reliability polynomials.

Compositions were compared with hammocks according to three FoMs: RII, the slope of
the reliability polynomials and their variations. For the particular cases considered here we
have observed that compositions come very close to hammocks, without surpassing them. Still,
compositions of series and parallel present several advantages. There are compositions performing
almost as well as hammocks, while having fewer wires than hammocks, for the same number of
devices. We also noticed that there is a signi�cant computational gap, the reliability polynomials
of compositions being much simpler/easier to compute and analyze exactly.

Acknowledgement

Research supported in part by the European Union (EU) through the European Research
Development Fund (ERDF) under the Competitiveness Operational Program (COP): BioCell-
NanoART = Novel Bio-inspired Cellular Nano-architectures, POC-A1-A1.1.4-E nr. 30/01.09.2016.

Bibliography

[1] Beiu, V.; Cowell, S.R.; Dr goi, V.; Hoar , S.; Ga³par, P. (2018); Hammocks versus ham-
mock, 2018 7th International Conference on Computers Communications and Control (IC-
CCC), Proc. of, Oradea, Romania, May 2018, Publisher: IEEE, 119�123, 2018. DOI:
10.1109/ICCCC.2018.8390447

[2] Beiu, V.; L. D u³, L.; Rohatinovici, N.-C.; B la³, V. E. (2018); Transport reliability on
axonal cytoskeleton, Proc. Intl. Conf. Eng. Modern Electr. Syst. (EMES), Oradea, Romania,
Jun. 2017, 160�163, 2017.

[3] Ball, M.O.; Colbourn, C.J.; Provan, J.S. (1992); Network reliability, Tech. Rep. TR 92-74,
Systems Research Center/ Institute for System Research, University of Maryland, College
Park, MD, USA, June 1992.

[4] Barlow, R. E.; Proschan, F. (1965); Mathematical Theory of Reliability, John Wiley & Sons,
New York, NY, 1965.

[5] Colbourn, C.J. (1991); Combinatorial aspects of network reliability, Annals of Operations
Research, 33(1), 3 � 15, Jan. 1991.

[6] Courtland, R. (2016); The next high-performance transistor, IEEE Spectr., 53(10), 11�12,
Oct. 2016.

[7] Cowell, S.R.; Beiu, V.; D u³, L.; Poulin, P. (2018); On the exact reliability enhancements
of small hammock networks, IEEE Access, 6(1), 25411�25426, Apr. 2018. [Early version as
"On hammock networks � Sixty years after", Proc. Intl. Conf. Design & Technol. Integr.
Syst. Nanoscale Era (DTIS), Palma de Mallorca, Spain, Apr. 2017, art. 7929871]

[8] Cowell, S.R.; Beiu, V.; D u³, L.; Poulin, P. (2017); On cylindrical hammock networks, Proc.
Intl. Conf. Nanotech. (IEEE-NANO), Pittsburgh, PA, USA, Jul. 2017, 185�188, 2017.



How Reliable are Compositions of Series and Parallel Networks
Compared with Hammocks? 791

[9] Deng, H.; Chen, J.; Q. Li,Q.; Li,R.; Gao, Q. (2004); On the construction of most reliable
networks, Discr. Appl. Maths., 140(1-3), 19�33, 2004.

[10] Dr goi, V.; Cowell, S.R.; Hoar , S.; Ga³par, P.; Beiu, V. (2018); Can series and parallel
compositions improve on hammocks?, Proc. of 2018 7th International Conference on Com-
puters Communications and Control (ICCCC), Oradea, Romania, May 2018, Publisher:
IEEE, 124�130, 2018. DOI: 10.1109/ICCCC.2018.8390448

[11] Du�n, R.J. (1965); Topology of series-parallel networks, Journal of Mathematical Analysis
and Applications, 10(2), 303�318, 1965.

[12] Geppert, L. (2002); The amazing vanishing transistor act, IEEE Spectr., 239(10), 8�33,
2002.

[13] IEEE Rebooting Computing, https://rebootingcomputing.ieee.org/

[14] International Roadmap for Devices and Systems, (IRDS), 2017 [Online]. Available:
https://irds.ieee.org/roadmap-2017

[15] Klaschka, T.F. (1967); Two contributions to redundancy theory, Proc. Annual Symposium
on Switching and Automata Theory (SWAT), Austin, TX, USA, Oct. 1967, 175�183, 1967.
doi: 10.1109/FOCS.1967.36

[16] Klaschka, T.F. (1971); A method for redundancy scheme performance assessment, IEEE
Transactions on Computers, C-20(11), 1371�1376, 1971. doi: 10.1109/T-C.1971.223141

[17] Kuo, W.; Zuo, M.J. (2003); Optimal Reliability Modeling: Principles and Applications, J.
Wiley & Sons, Hoboken, NJ, USA, 2003.

[18] Lee, C.Y. (1955); Analysis of switching networks, Bell System Technical Journal, 34(6),
1287�1315, 1955. doi:10.1002/j.1538-7305.1955.tb03799

[19] Li, Q.; Li, Q. (1998); Reliability analysis of circulant graphs, Networks, 31(2), 61�65, Mar.
1998.

[20] Moore, E.F.; Shannon, C.E. (1956); Reliable circuits using less reliable relays � Part I, J.
Frankl. Inst., 262(3), 191�208, 1956.

[21] Moore, E.F.; Shannon, C.E. (1956); Reliable circuits using less reliable relays � Part II, J.
Frankl. Inst., 262(4), 281�297, 1956.

[22] von Neumann, J. (1952, 1956); Probabilistic logics and the synthesis of reliable organisms
from unreliable components, Jan. 1952 . Also in C. E. Shannon, and J. McCarthy (Eds.):
Automata Studies, Princeton Univ. Press, Princeton, NJ, USA, 43�98, Apr. 1956.

[23] Theis, T.N.; Wong, H.-S.P. (2017); The end of Moore's law: A new beginning for information
technology, Comput. Sci. & Eng., 19(2), 41�50, 2017.

[24] Wald, J.A.; Colbourn, C.J. (1983); Steiner trees, partial 2-trees, and minimum IFI networks,
Networks, vol. 13, no. 2, pp. 13(2), 159�167, 1983. doi:10.1002/net.3230130202

[25] Weichenberg, G.E.; Chan, V.W.S.; Medard, M. (2004); High-reliability topological architec-
tures for networks under stress, IEEE J. Sel. Areas Comm., 22(9), 1830�1845, 2004.

[26] Williams, R.S. (2017); What's next?, Comput. Sci. & Eng., 19(2), 7�13, 2017.