# Representing Tactics for Fault Recovery: A Reconfigurable, Modular, and Hierarchical Approach

Authors: Fernando J. Barros
Journal: International Journal of Reconfigurable Computing
 (2015)

---

## Abstract

We show the advantages of modular and hierarchical
design in obtaining fault-tolerant software. Modularity enables
the identification of faulty software units simplifying key
operations, like software removal and replacement. We describe
three approaches to repair faulty software based on replication,
namely, Passive Replication, N-Version Replication, and Active Replication,
based on modular components. We show that the key construct to
represent these tactics is the ability to makead hoc
changes in software topologies. We consider hierarchical mobility
as a useful operation to introduce new software units for
replacing faulty ones. For illustration purposes, we use
connecton, a hierarchical, modular, and self-modifying software
specification formalism, and its implementation in the Desmos
framework.


---

## Body

## 1. Introduction

Replication is commonly used as the basis for enabling fault tolerance. In this technique, critical software modules are replicated, and, upon fault detection, theerroneous units are removed and service is provided by the remainingcorrect modules. There are several tactics for supporting replication that differ in the manner service is kept active upon a fault. We consider herePassive Replication,Active Replication [1], andN-Version programming [2] approaches. The development of fault-tolerant software depends on the ability to identify and remove the faulty code.Modular and hierarchical software enables the development of software units with well-defined input and output interfaces [3]. Due to these characteristics, modular software units are easy to identify and, if required, to replace. In this paper we exploit the ability of modular software to be used as a framework for representing resilient software. We note that object-oriented programming does not supportfull modularity, as defined in this work, since objects only provide input interface missingoutput interfaces.The ability to repair a network of software units is enabled by the capability to support structural changes in the software topology [4]. In particular, the basic operation required to achieve software repair is the ability to remove a faulty unit and eventually to replace it by a nonfaulty instance.We have developedconnectons [3], a modular and hierarchical approach to software development that is based on the request-reply principles of object-oriented programming. These characteristics makeconnectons compatible with the current approaches of object-oriented software design while improving this design with modular constructs.Connectons support the basic primitives for replacing faulty software units and to makead hoc changes in software topologies. In particular,connectons can representhierarchical mobility [5], a useful construct to replace or to update software units during runtime. Desmos, a Smalltalk implementation ofconnectons, provides full support for modular and hierarchical software with dynamic topology.Common fault-tolerance techniques based on replication are described in Desmos providing the proof of concept for modular and hierarchical development of resilient software. A more general discussion on software fault tolerance and reliability can be found in [6–8].The paper is organized as follows. Section2 provides a formal definition of basic and ensembleconnectons. Desmos, the Smalltalk implementation ofconnectons, is described in Section 3. Section 4 provides the realization of the Passive Replication tactic usingconnectons. Active Replication is described in Section 5. N-Version Replication using component mobility is discussed in Section 6. A comparison of these approaches and a description of related work are presented in Section 7. Conclusions and future work are given in Section 8.


## 2. Connectons

Connectons define two types of software units: basic and ensemble connectons. Basic connectons provide the actual method invocation, whereas ensembles are a composition of connectons and provide message passing. In component composition, basic and ensemble connectons can be used indistinctly.Connectons support a modular and hierarchical type of software construction. Ensemble definition is dynamic, enabling the definition of self-modifying software topologies. We refer here to software units asconnectons, while theconnections between connectons are referred to aslinks orchannels.


### 2.1. Basic Connecton

Each connecton has its own description, referred to as theconnecton model. Let B
^ be the set of names of basic connectons. The connecton model associated with χ
∈
B
^ is given by (1)
M
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
S
,
s
0
,
a
g
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
χ
,where i
n
G
a
t
e
s is the set of connecton input gates, i
n
S
i
g
n
g is the input-output signature of every gate g in i
n
G
a
t
e
s, S is the set of connecton states, s
0 is the connecton initial state, a
g is an action for every gate g belonging to set i
n
G
a
t
e
s, o
u
t
G
a
t
e
s is the set of connecton output gates, o
u
t
S
i
g
n
k is the output-to-input signature of every gate k in o
u
t
G
a
t
e
s, o
u
t
I
S
i
g
n
k is intermediate signature of every output gate k
∈
o
u
t
G
a
t
e
s, and o
u
t
F
u
n
c
t
i
o
n
k is the output function of every gate k in o
u
t
G
a
t
e
s.An input signature is a 2-tuple containing the range set of the incoming parameters and the range set of outgoing parameters. For example, if input gateg receives real values R and responds by sending integer values I, then its input signature is given by i
n
S
i
g
n
g
=
(
R
,
I
).The functiona
g on input gate g of signature (
I
g
,
O
g
) is expressed by(2)
a
g
:
S
×
I
g
⇝
S
×
O
g
.Anaction corresponds to a method in the object paradigm. Action a
g receives input values from (
S
×
I
g
), produces a change in the connecton state, and returns a value from O
g. As a side effect, an action on a connecton can trigger other actions on the connectons linked to it. Actions are considered here asstochastic functions. Although actions define partially a deterministic behavior, their overall behavior is generally stochastic since it depends on the results produced by the external connectons. These values are usually unknown, since they depend on the specific topology a connecton is part of and on the links that are established by the topology.An output signature is a 2-tuple containing the range set of the outgoing parameters and the range set of incoming parameters. Output functions convert the set of values received by an output gate. These functions are useful when several channels are linked to an output gate and, in general, to convert values without creating special connectons.The output functiono
u
t
F
u
n
c
t
i
o
n
k on output gate k of intermediate signature D
k and output signature (
O
k
,
I
k
) is expressed by(3)
o
u
t
F
u
n
c
t
i
o
n
k
:
D
k
∗
⟶
I
k
,where D
k
∗ is a sequence of values from set D
k.Given an output gatek with output signature (
O
k
,
I
k
), we use the following definitions to simplify the specification, when the output function o
u
t
F
u
n
c
t
i
o
n
k and the intermediate input signature D
k are omitted: (4)
D
k
=
I
k
o
u
t
F
u
n
c
t
i
o
n
k
=
⌀
o
u
t
F
u
n
c
t
i
o
n
k
⌀
∣
t
=
o
u
t
F
u
n
c
t
i
o
n
k
t
o
u
t
F
u
n
c
t
i
o
n
k
h
∣
_
=
h
,where ⌀ represents the absence of value and [
] represents the empty list.


#### 2.1.1. Position Connecton

To illustrate an example of a basic connecton, we employ thePosition entity represented in Figure 1. This connecton has three input gates:time:ax:,x:, andstate:, corresponding to actions defined in the connecton.Position has also the output gatebackup: corresponding to the backup services the connecton can request to the exterior.Position receives piecewise constant acceleration values and computes the current position x by double integrating the input signal. For simplicity we describe here one-dimension positions. 2D coordinates are used in the next sections.Figure 1
Position connecton.Position state keeps the time of the last update (
t
i
m
e
), position (
x
), velocity (
v
x
), and acceleration (
a
x
) values. This connecton is described byM
P
o
s
i
t
i
o
n
=
(
{
s
t
a
t
e
:
,
t
i
m
e
:
a
x
:
,
x
:
},
{
(
R
4
,
∅
)
,
(
R
2
,
∅
)
,
(
R
,
R
)
},
R
4
,
(
t
i
m
e
=
0
,
x
=
0
,
v
x
=
0
,
a
x
=
0
),
{
a
c
t
i
o
n
s
t
a
t
e
:
,
a
c
t
i
o
n
t
i
m
e
:
a
x
:
,
a
c
t
i
o
n
x
:
},
{
b
a
c
k
u
p
:
}
,
{
(
R
4
,
∅
)
}
)The state is set by action:a
c
t
i
o
n
s
t
a
t
e
:
(
s
)
t
i
m
e
,
x
,
v
x
,
a
x
←
sState variables are updated when the acceleration changes by the action:a
c
t
i
o
n
t
i
m
e
:
a
x
:
(
t
,
a
)
δ
←
t
-
t
i
m
e
x
←
x
+
v
x
δ
+
a
x
/
2
δ
2
v
x
←
v
x
+
a
x
δ
a
x
←
a
t
i
m
e
←
t
o
u
t
b
a
c
k
u
p
:
t
i
m
e
,
x
,
v
x
,
a
xThis action sends the current state to the outside through gatebackup:, so it can be stored in other connectons for backup purposes. The current position at time t is computed bya
c
t
i
o
n
x
:
(
t
)
δ
←
t
-
t
i
m
e
↑
x
+
v
x
δ
+
a
x
/
2
δ
2This action does not change the state variables and thus the current state is not to be saved.


### 2.2. Ensemble Connecton

Hierarchical composition of systems has been used as a powerful heuristic to manage complex systems. We consider that connectons can be hierarchically composed, being the resultant connecton indistinguishable from the basic connecton of the last section. This ability permits handling in a homogeneous form both basic and aggregated components. A connecton ensemble (network) is a complex connecton built by the composition of other connectons. LetE
^ be the set of names corresponding to connecton ensembles, constrained to E
^
∩
B
^
=
∅. The model of the ensemble connecton χ
∈
E
^ is defined by (5)
M
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
i
n
I
S
i
g
n
g
,
i
n
F
u
n
c
t
i
o
n
g
,
ɛ
,
M
ɛ
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
χ
,where i
n
G
a
t
e
s is the set of the ensemble input gates, i
n
S
i
g
n
g is the input-output signature of every gate g
∈
i
n
G
a
t
e
s, i
n
I
S
i
g
n
g is the intermediate signature of every input gate g
∈
i
n
G
a
t
e
s, i
n
F
u
n
c
t
i
o
n
g is the input function of every gate g
∈
i
n
G
a
t
e
s
,
ɛ
∈
ɛ
^ is the ensemble executive, M
ɛ is the model of the ensemble executive, o
u
t
G
a
t
e
s is the set of the ensemble output gates, o
u
t
S
i
g
n
k is the output-to-input signature of every gate k
∈
o
u
t
G
a
t
e
s, o
u
t
I
S
i
g
n
k is the intermediate signature of every output gate k
∈
o
u
t
G
a
t
e
s, and o
u
t
F
u
n
c
t
i
o
n
k is the output function of every gate k
∈
o
u
t
G
a
t
e
s with ɛ
^ representing the set of all names associated with ensemble executives, constrained to ɛ
^
∩
B
^
=
ɛ
^
∩
E
^
=
∅.The default signatures and input/output functions defined in Section2.1 are used to simplify the ensemble specification.The connecton ensemble has the same type of interface of a basic connecton making it possible to use ensembles as components of other ensembles, enabling the hierarchical composition of connectons. The ensemble structure is managed by a special connecton termed hereensemble executive
ϵ. The executive keeps a list of the connectons that compose the ensemble. It also keeps the set of the channels existing among connectons. This information is not static and can be changed by executive actions. The model of the ensemble executive is an augmented connecton model defined by (6)
M
ε
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
S
,
s
0
,
a
g
,
σ
,
Σ
^
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
ε
χ
.Functionσ maps the executive state into an ensemble structure. Thestructure function
σ is expressed by(7)
σ
:
S
⟶
Σ
^
.Each structure Σ
∈
Σ
^ is given by(8)
Σ
=
C
,
M
c
,
L
,
Ξ
,where C is the set of connectons, M
c is the model of each connecton c
∈
C, L is a set of channels, and Ξ is the order function.Given that the current ensemble structure is a function of the executive state, any change in this state can cause a structural change in the ensemble. A channel inL is a 3-tuple defined by(9)
i
,
g
i
,
j
,
g
j
,
dF
,
rF
,where i is the name of the source connecton, g
i is a gate of the i connecton, j is the receiver connecton, g
j is a gate of j, dF is the channel direct filter, and rF is the channel reverse filter.Filters transform both the values sent and received by a connecton. For example, if a connecton works with values in m·s−1 and needs to communicate with another connecton operating in km·h−1, then filtering capabilities provide a solution to make this conversion without the creation of additional connectons. In this case, the direct filter would be given by dF
(
x
)
=
3.6
x, and the reverse filter would be given by rF
(
x
)
=
x
/
3.6 to make the conversions m·s−1
⇄ km·h−1. If omitted, filters are considered to be the identity function.Ξ
:
L
+
→
L
+ is theorder function, where L
+ is the set of all sets of channels (excluding the empty set).The order function establishes the order of the outside calls when several channels are linked from the same output gate. For simplicity, when omitted, a nondeterministic order is assumed.The initial structure of the ensembleΣ
0 is given by Σ
0
=
σ
(
s
0
,
ϵ
).


#### 2.2.1. Example: Testing Position

To illustrate the definition of an ensemble, we build a connecton to test thePosition connecton of Section 2.2. The ensemble is depicted in Figure 2 and it is defined by(10)
M
P
o
s
i
t
i
o
n
T
e
s
t
=
x
,
∅
,
R
,
ϵ
,
M
ϵ
,where(11)
M
ϵ
=
x
,
∅
,
R
,
s
0
,
s
1
,
…
,
s
0
,
a
c
t
i
o
n
x
,
t
i
m
e
:
a
x
:,
x
:
,
R
2
,
∅
,
R
,
R
,
σ
,
Σ
^
.The ensemble has a single static structure given by(12)
σ
s
0
=
σ
s
1
=
⋯
=
C
,
M
c
,
L
,where C
=
{
P
o
s
i
t
i
o
n
}
{
M
c
}
=
{
M
P
o
s
i
t
i
o
n
}
L
=
{
(
(
P
o
s
i
t
i
o
n
T
e
s
t
,
x
)
,
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
)
),
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
t
i
m
e
:
a
x
:
),
(
P
o
s
i
t
i
o
n
,
t
i
m
e
:
a
x
:
)
)
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
:
)
,
(
P
o
s
i
t
i
o
n
,
x
:
)
)Figure 2
Block diagram of thePositionTest ensemble.The connecton ensemble, represented in Figure2, is composed of onePosition connecton, linked to the executive P
o
s
i
t
i
o
n
T
e
s
t
ϵ. The ensemble has the input gatex to access the value of the current position. The executive requests the position through the callx:
t
i
m
e, where t
i
m
e represents the current time.The executive updates at a regular interval the current value of accelerationa
x through gatetime:ax:. This value is integrated by connectonPosition that computes current position and velocity as described in the last section. Output gatebackup: is not linked and messages sent through this gate are just ignored.


### 2.3. Kinds of Structural Changes

Software ensembles can undergo arbitrary structural changes. These changes include the ability to add and remove connectons and the capability to modify the channels among connectons. The kinds of structural changes are illustrated with ensemble connectonD represented in Figure 3. The ensembleD is initially empty except for the executive D
ϵ as depicted in Figure 3(a). The executive D
ϵ creates connectonA and adds channels between the ensemblesD andA and betweenA andD, as represented in Figure 3(b). The next change involves the addition of connectonB, the creation of a channel fromB toD, the deletion of the channel fromA toD, and the creation of a channel fromA toB, as depicted in Figure 3(c). Finally, connectonA is deleted and a channel is created fromD toB, as represented in Figure 3(d). We note that sinceconnectons support hierarchical software units,A andB can be either basic or ensemble connectons. Due to the reflective capabilities of the executive, structural decisions can be made taking into account the current ensemble structure. This gives the possibility of making changes based, for example, on the number of connectons or channels currently present in the ensemble. Another form of topology adaptation involves the transmission of a connecton between two ensembles [5] and is termed herehierarchical mobility.Figure 3
Structural changes.
(a)
(b)
(c)
(d)


## 2.1. Basic Connecton

Each connecton has its own description, referred to as theconnecton model. Let B
^ be the set of names of basic connectons. The connecton model associated with χ
∈
B
^ is given by (1)
M
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
S
,
s
0
,
a
g
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
χ
,where i
n
G
a
t
e
s is the set of connecton input gates, i
n
S
i
g
n
g is the input-output signature of every gate g in i
n
G
a
t
e
s, S is the set of connecton states, s
0 is the connecton initial state, a
g is an action for every gate g belonging to set i
n
G
a
t
e
s, o
u
t
G
a
t
e
s is the set of connecton output gates, o
u
t
S
i
g
n
k is the output-to-input signature of every gate k in o
u
t
G
a
t
e
s, o
u
t
I
S
i
g
n
k is intermediate signature of every output gate k
∈
o
u
t
G
a
t
e
s, and o
u
t
F
u
n
c
t
i
o
n
k is the output function of every gate k in o
u
t
G
a
t
e
s.An input signature is a 2-tuple containing the range set of the incoming parameters and the range set of outgoing parameters. For example, if input gateg receives real values R and responds by sending integer values I, then its input signature is given by i
n
S
i
g
n
g
=
(
R
,
I
).The functiona
g on input gate g of signature (
I
g
,
O
g
) is expressed by(2)
a
g
:
S
×
I
g
⇝
S
×
O
g
.Anaction corresponds to a method in the object paradigm. Action a
g receives input values from (
S
×
I
g
), produces a change in the connecton state, and returns a value from O
g. As a side effect, an action on a connecton can trigger other actions on the connectons linked to it. Actions are considered here asstochastic functions. Although actions define partially a deterministic behavior, their overall behavior is generally stochastic since it depends on the results produced by the external connectons. These values are usually unknown, since they depend on the specific topology a connecton is part of and on the links that are established by the topology.An output signature is a 2-tuple containing the range set of the outgoing parameters and the range set of incoming parameters. Output functions convert the set of values received by an output gate. These functions are useful when several channels are linked to an output gate and, in general, to convert values without creating special connectons.The output functiono
u
t
F
u
n
c
t
i
o
n
k on output gate k of intermediate signature D
k and output signature (
O
k
,
I
k
) is expressed by(3)
o
u
t
F
u
n
c
t
i
o
n
k
:
D
k
∗
⟶
I
k
,where D
k
∗ is a sequence of values from set D
k.Given an output gatek with output signature (
O
k
,
I
k
), we use the following definitions to simplify the specification, when the output function o
u
t
F
u
n
c
t
i
o
n
k and the intermediate input signature D
k are omitted: (4)
D
k
=
I
k
o
u
t
F
u
n
c
t
i
o
n
k
=
⌀
o
u
t
F
u
n
c
t
i
o
n
k
⌀
∣
t
=
o
u
t
F
u
n
c
t
i
o
n
k
t
o
u
t
F
u
n
c
t
i
o
n
k
h
∣
_
=
h
,where ⌀ represents the absence of value and [
] represents the empty list.


### 2.1.1. Position Connecton

To illustrate an example of a basic connecton, we employ thePosition entity represented in Figure 1. This connecton has three input gates:time:ax:,x:, andstate:, corresponding to actions defined in the connecton.Position has also the output gatebackup: corresponding to the backup services the connecton can request to the exterior.Position receives piecewise constant acceleration values and computes the current position x by double integrating the input signal. For simplicity we describe here one-dimension positions. 2D coordinates are used in the next sections.Figure 1
Position connecton.Position state keeps the time of the last update (
t
i
m
e
), position (
x
), velocity (
v
x
), and acceleration (
a
x
) values. This connecton is described byM
P
o
s
i
t
i
o
n
=
(
{
s
t
a
t
e
:
,
t
i
m
e
:
a
x
:
,
x
:
},
{
(
R
4
,
∅
)
,
(
R
2
,
∅
)
,
(
R
,
R
)
},
R
4
,
(
t
i
m
e
=
0
,
x
=
0
,
v
x
=
0
,
a
x
=
0
),
{
a
c
t
i
o
n
s
t
a
t
e
:
,
a
c
t
i
o
n
t
i
m
e
:
a
x
:
,
a
c
t
i
o
n
x
:
},
{
b
a
c
k
u
p
:
}
,
{
(
R
4
,
∅
)
}
)The state is set by action:a
c
t
i
o
n
s
t
a
t
e
:
(
s
)
t
i
m
e
,
x
,
v
x
,
a
x
←
sState variables are updated when the acceleration changes by the action:a
c
t
i
o
n
t
i
m
e
:
a
x
:
(
t
,
a
)
δ
←
t
-
t
i
m
e
x
←
x
+
v
x
δ
+
a
x
/
2
δ
2
v
x
←
v
x
+
a
x
δ
a
x
←
a
t
i
m
e
←
t
o
u
t
b
a
c
k
u
p
:
t
i
m
e
,
x
,
v
x
,
a
xThis action sends the current state to the outside through gatebackup:, so it can be stored in other connectons for backup purposes. The current position at time t is computed bya
c
t
i
o
n
x
:
(
t
)
δ
←
t
-
t
i
m
e
↑
x
+
v
x
δ
+
a
x
/
2
δ
2This action does not change the state variables and thus the current state is not to be saved.


## 2.1.1. Position Connecton

To illustrate an example of a basic connecton, we employ thePosition entity represented in Figure 1. This connecton has three input gates:time:ax:,x:, andstate:, corresponding to actions defined in the connecton.Position has also the output gatebackup: corresponding to the backup services the connecton can request to the exterior.Position receives piecewise constant acceleration values and computes the current position x by double integrating the input signal. For simplicity we describe here one-dimension positions. 2D coordinates are used in the next sections.Figure 1
Position connecton.Position state keeps the time of the last update (
t
i
m
e
), position (
x
), velocity (
v
x
), and acceleration (
a
x
) values. This connecton is described byM
P
o
s
i
t
i
o
n
=
(
{
s
t
a
t
e
:
,
t
i
m
e
:
a
x
:
,
x
:
},
{
(
R
4
,
∅
)
,
(
R
2
,
∅
)
,
(
R
,
R
)
},
R
4
,
(
t
i
m
e
=
0
,
x
=
0
,
v
x
=
0
,
a
x
=
0
),
{
a
c
t
i
o
n
s
t
a
t
e
:
,
a
c
t
i
o
n
t
i
m
e
:
a
x
:
,
a
c
t
i
o
n
x
:
},
{
b
a
c
k
u
p
:
}
,
{
(
R
4
,
∅
)
}
)The state is set by action:a
c
t
i
o
n
s
t
a
t
e
:
(
s
)
t
i
m
e
,
x
,
v
x
,
a
x
←
sState variables are updated when the acceleration changes by the action:a
c
t
i
o
n
t
i
m
e
:
a
x
:
(
t
,
a
)
δ
←
t
-
t
i
m
e
x
←
x
+
v
x
δ
+
a
x
/
2
δ
2
v
x
←
v
x
+
a
x
δ
a
x
←
a
t
i
m
e
←
t
o
u
t
b
a
c
k
u
p
:
t
i
m
e
,
x
,
v
x
,
a
xThis action sends the current state to the outside through gatebackup:, so it can be stored in other connectons for backup purposes. The current position at time t is computed bya
c
t
i
o
n
x
:
(
t
)
δ
←
t
-
t
i
m
e
↑
x
+
v
x
δ
+
a
x
/
2
δ
2This action does not change the state variables and thus the current state is not to be saved.


## 2.2. Ensemble Connecton

Hierarchical composition of systems has been used as a powerful heuristic to manage complex systems. We consider that connectons can be hierarchically composed, being the resultant connecton indistinguishable from the basic connecton of the last section. This ability permits handling in a homogeneous form both basic and aggregated components. A connecton ensemble (network) is a complex connecton built by the composition of other connectons. LetE
^ be the set of names corresponding to connecton ensembles, constrained to E
^
∩
B
^
=
∅. The model of the ensemble connecton χ
∈
E
^ is defined by (5)
M
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
i
n
I
S
i
g
n
g
,
i
n
F
u
n
c
t
i
o
n
g
,
ɛ
,
M
ɛ
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
χ
,where i
n
G
a
t
e
s is the set of the ensemble input gates, i
n
S
i
g
n
g is the input-output signature of every gate g
∈
i
n
G
a
t
e
s, i
n
I
S
i
g
n
g is the intermediate signature of every input gate g
∈
i
n
G
a
t
e
s, i
n
F
u
n
c
t
i
o
n
g is the input function of every gate g
∈
i
n
G
a
t
e
s
,
ɛ
∈
ɛ
^ is the ensemble executive, M
ɛ is the model of the ensemble executive, o
u
t
G
a
t
e
s is the set of the ensemble output gates, o
u
t
S
i
g
n
k is the output-to-input signature of every gate k
∈
o
u
t
G
a
t
e
s, o
u
t
I
S
i
g
n
k is the intermediate signature of every output gate k
∈
o
u
t
G
a
t
e
s, and o
u
t
F
u
n
c
t
i
o
n
k is the output function of every gate k
∈
o
u
t
G
a
t
e
s with ɛ
^ representing the set of all names associated with ensemble executives, constrained to ɛ
^
∩
B
^
=
ɛ
^
∩
E
^
=
∅.The default signatures and input/output functions defined in Section2.1 are used to simplify the ensemble specification.The connecton ensemble has the same type of interface of a basic connecton making it possible to use ensembles as components of other ensembles, enabling the hierarchical composition of connectons. The ensemble structure is managed by a special connecton termed hereensemble executive
ϵ. The executive keeps a list of the connectons that compose the ensemble. It also keeps the set of the channels existing among connectons. This information is not static and can be changed by executive actions. The model of the ensemble executive is an augmented connecton model defined by (6)
M
ε
χ
=
i
n
G
a
t
e
s
,
i
n
S
i
g
n
g
,
S
,
s
0
,
a
g
,
σ
,
Σ
^
,
o
u
t
G
a
t
e
s
,
o
u
t
S
i
g
n
k
,
o
u
t
I
S
i
g
n
k
,
o
u
t
F
u
n
c
t
i
o
n
k
ε
χ
.Functionσ maps the executive state into an ensemble structure. Thestructure function
σ is expressed by(7)
σ
:
S
⟶
Σ
^
.Each structure Σ
∈
Σ
^ is given by(8)
Σ
=
C
,
M
c
,
L
,
Ξ
,where C is the set of connectons, M
c is the model of each connecton c
∈
C, L is a set of channels, and Ξ is the order function.Given that the current ensemble structure is a function of the executive state, any change in this state can cause a structural change in the ensemble. A channel inL is a 3-tuple defined by(9)
i
,
g
i
,
j
,
g
j
,
dF
,
rF
,where i is the name of the source connecton, g
i is a gate of the i connecton, j is the receiver connecton, g
j is a gate of j, dF is the channel direct filter, and rF is the channel reverse filter.Filters transform both the values sent and received by a connecton. For example, if a connecton works with values in m·s−1 and needs to communicate with another connecton operating in km·h−1, then filtering capabilities provide a solution to make this conversion without the creation of additional connectons. In this case, the direct filter would be given by dF
(
x
)
=
3.6
x, and the reverse filter would be given by rF
(
x
)
=
x
/
3.6 to make the conversions m·s−1
⇄ km·h−1. If omitted, filters are considered to be the identity function.Ξ
:
L
+
→
L
+ is theorder function, where L
+ is the set of all sets of channels (excluding the empty set).The order function establishes the order of the outside calls when several channels are linked from the same output gate. For simplicity, when omitted, a nondeterministic order is assumed.The initial structure of the ensembleΣ
0 is given by Σ
0
=
σ
(
s
0
,
ϵ
).


### 2.2.1. Example: Testing Position

To illustrate the definition of an ensemble, we build a connecton to test thePosition connecton of Section 2.2. The ensemble is depicted in Figure 2 and it is defined by(10)
M
P
o
s
i
t
i
o
n
T
e
s
t
=
x
,
∅
,
R
,
ϵ
,
M
ϵ
,where(11)
M
ϵ
=
x
,
∅
,
R
,
s
0
,
s
1
,
…
,
s
0
,
a
c
t
i
o
n
x
,
t
i
m
e
:
a
x
:,
x
:
,
R
2
,
∅
,
R
,
R
,
σ
,
Σ
^
.The ensemble has a single static structure given by(12)
σ
s
0
=
σ
s
1
=
⋯
=
C
,
M
c
,
L
,where C
=
{
P
o
s
i
t
i
o
n
}
{
M
c
}
=
{
M
P
o
s
i
t
i
o
n
}
L
=
{
(
(
P
o
s
i
t
i
o
n
T
e
s
t
,
x
)
,
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
)
),
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
t
i
m
e
:
a
x
:
),
(
P
o
s
i
t
i
o
n
,
t
i
m
e
:
a
x
:
)
)
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
:
)
,
(
P
o
s
i
t
i
o
n
,
x
:
)
)Figure 2
Block diagram of thePositionTest ensemble.The connecton ensemble, represented in Figure2, is composed of onePosition connecton, linked to the executive P
o
s
i
t
i
o
n
T
e
s
t
ϵ. The ensemble has the input gatex to access the value of the current position. The executive requests the position through the callx:
t
i
m
e, where t
i
m
e represents the current time.The executive updates at a regular interval the current value of accelerationa
x through gatetime:ax:. This value is integrated by connectonPosition that computes current position and velocity as described in the last section. Output gatebackup: is not linked and messages sent through this gate are just ignored.


## 2.2.1. Example: Testing Position

To illustrate the definition of an ensemble, we build a connecton to test thePosition connecton of Section 2.2. The ensemble is depicted in Figure 2 and it is defined by(10)
M
P
o
s
i
t
i
o
n
T
e
s
t
=
x
,
∅
,
R
,
ϵ
,
M
ϵ
,where(11)
M
ϵ
=
x
,
∅
,
R
,
s
0
,
s
1
,
…
,
s
0
,
a
c
t
i
o
n
x
,
t
i
m
e
:
a
x
:,
x
:
,
R
2
,
∅
,
R
,
R
,
σ
,
Σ
^
.The ensemble has a single static structure given by(12)
σ
s
0
=
σ
s
1
=
⋯
=
C
,
M
c
,
L
,where C
=
{
P
o
s
i
t
i
o
n
}
{
M
c
}
=
{
M
P
o
s
i
t
i
o
n
}
L
=
{
(
(
P
o
s
i
t
i
o
n
T
e
s
t
,
x
)
,
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
)
),
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
t
i
m
e
:
a
x
:
),
(
P
o
s
i
t
i
o
n
,
t
i
m
e
:
a
x
:
)
)
(
(
P
o
s
i
t
i
o
n
T
e
s
t
ϵ
,
x
:
)
,
(
P
o
s
i
t
i
o
n
,
x
:
)
)Figure 2
Block diagram of thePositionTest ensemble.The connecton ensemble, represented in Figure2, is composed of onePosition connecton, linked to the executive P
o
s
i
t
i
o
n
T
e
s
t
ϵ. The ensemble has the input gatex to access the value of the current position. The executive requests the position through the callx:
t
i
m
e, where t
i
m
e represents the current time.The executive updates at a regular interval the current value of accelerationa
x through gatetime:ax:. This value is integrated by connectonPosition that computes current position and velocity as described in the last section. Output gatebackup: is not linked and messages sent through this gate are just ignored.


## 2.3. Kinds of Structural Changes

Software ensembles can undergo arbitrary structural changes. These changes include the ability to add and remove connectons and the capability to modify the channels among connectons. The kinds of structural changes are illustrated with ensemble connectonD represented in Figure 3. The ensembleD is initially empty except for the executive D
ϵ as depicted in Figure 3(a). The executive D
ϵ creates connectonA and adds channels between the ensemblesD andA and betweenA andD, as represented in Figure 3(b). The next change involves the addition of connectonB, the creation of a channel fromB toD, the deletion of the channel fromA toD, and the creation of a channel fromA toB, as depicted in Figure 3(c). Finally, connectonA is deleted and a channel is created fromD toB, as represented in Figure 3(d). We note that sinceconnectons support hierarchical software units,A andB can be either basic or ensemble connectons. Due to the reflective capabilities of the executive, structural decisions can be made taking into account the current ensemble structure. This gives the possibility of making changes based, for example, on the number of connectons or channels currently present in the ensemble. Another form of topology adaptation involves the transmission of a connecton between two ensembles [5] and is termed herehierarchical mobility.Figure 3
Structural changes.
(a)
(b)
(c)
(d)


## 3. TheDesmos Software System

The Desmos software system provides an implementation ofconnectons in the Smalltalk language. Smalltalk proved to be an excellent prototyping language offering many constructs not commonly provided bymainstream object-oriented languages, for example, block closures, used in filter implementation.


### 3.1. Desmos Organization

In the Desmos software system, connecton models are hierarchically organized.Desmos::Model is the root model for all connecton models. ModelExecutive is the base connecton model of all ensemble executives. This model implements all basic operations that support changes in connecton network structure. Operations include adding and deleting connectons and channels. Every specific domain ensemble executive must be a submodel of theExecutive model. Figure 4 represents a partial view of the Desmos hierarchy, as described above. All the submodels of the modeExecutive can inherit the structure of the parent model. TheExecutive model provides just an empty connecton ensemble and all the primitive operations that can be used to manage the ensemble structure.Figure 4
Desmos hierarchy.


### 3.2. Desmos Support for Structural Changes

The following methods are defined in the Desmos system to change the ensemble connecton structure during the execution of a program:(i)add: aName model: aModel adds to the ensemble a connecton namedaName and associates it with modelaModel.(ii)add: aConnecton name: aName addsaConnecton to the ensemble and names itaName.(iii)remove: aName removes a connecton namedaName from the ensemble. All channels from and to the removed connecton are removed.(iv)link: aName gate: aGate to: bName gate:
bGate creates a channel between two connectons.(v)link: aName gate: aGate to: bName gate:
bGate filter: dFilter filter: rFilter creates channel and filters between two connectons.(vi)unlink: aName gate: aGate from: bName
gate: bGate deletes a channel between two connectons.A connecton is referenced by its name. Names are assigned to connecton instances in the structure definition of the ensemble connecton.Connectons provide a uniform framework for defining component behavior and architectural changes. Executive methods responsible for the structural adaptations are intuitive to use due to the explicit representation of structure in the formalism.


## 3.1. Desmos Organization

In the Desmos software system, connecton models are hierarchically organized.Desmos::Model is the root model for all connecton models. ModelExecutive is the base connecton model of all ensemble executives. This model implements all basic operations that support changes in connecton network structure. Operations include adding and deleting connectons and channels. Every specific domain ensemble executive must be a submodel of theExecutive model. Figure 4 represents a partial view of the Desmos hierarchy, as described above. All the submodels of the modeExecutive can inherit the structure of the parent model. TheExecutive model provides just an empty connecton ensemble and all the primitive operations that can be used to manage the ensemble structure.Figure 4
Desmos hierarchy.


## 3.2. Desmos Support for Structural Changes

The following methods are defined in the Desmos system to change the ensemble connecton structure during the execution of a program:(i)add: aName model: aModel adds to the ensemble a connecton namedaName and associates it with modelaModel.(ii)add: aConnecton name: aName addsaConnecton to the ensemble and names itaName.(iii)remove: aName removes a connecton namedaName from the ensemble. All channels from and to the removed connecton are removed.(iv)link: aName gate: aGate to: bName gate:
bGate creates a channel between two connectons.(v)link: aName gate: aGate to: bName gate:
bGate filter: dFilter filter: rFilter creates channel and filters between two connectons.(vi)unlink: aName gate: aGate from: bName
gate: bGate deletes a channel between two connectons.A connecton is referenced by its name. Names are assigned to connecton instances in the structure definition of the ensemble connecton.Connectons provide a uniform framework for defining component behavior and architectural changes. Executive methods responsible for the structural adaptations are intuitive to use due to the explicit representation of structure in the formalism.


## 4. Passive Replication

Fault tolerance has been subjected to intense research in the last decades and several tactics have been developed to achieve resilient software. These approaches are mainly based on replication and on the ability to detect and to remove faulty software modules. We consider firstPassive Replication (PR). Other solutions are presented in next sections.In PR, one component (the primary) handles all the communication with the service requesters. When the primary updates its state, it backs up the state variables in the passive replicas. Fault tolerance is achieved by removing the primary replica when it becomes faulty and by promoting a backup replica to play the role of the primary. PR requires the state of the primary to be stored in all backup replicas so they can be used in case of failure.We consider a 2D variant ofPosition connecton described in Section 2.1 and used here in replication to achieve resilience. For illustration purposes, we use the connecton ensemble represented in Figure 5(a) and defined in Desmos by Listing 1. Fault detection usesheartbeat messages sent at regular intervals. Reverse filters are used in the ensemble definition since the executive needs not only to receive theheartbeats from connectonsA,B, andC but also to associate a name to each received value. The names missing are considered to correspond to faulty connectons.Listing 1:De
smos definition of the initial topology for Passive Replication.
(1)L
ocationP>>structure
(2)super structure.
(3)self link: #Network gate: #xy to: #Executive gate: #xy.
(4)self add: #A model: PositionP.
(5)self add: #B model: PositionP.
(6)self add: #C model: PositionP.
(7)self link: #Executive gate: #time:ax:ay: to: #A gate: #time:ax:ay:.
(8)  self link: #Executive gate: #xy: to: #A gate: #xy:.
(9)  self link: #A gate: #backup: to: #B gate: #state:.
(10)
self link: #A gate: #backup: to: #C gate: #state:.
(11) self link: #A gate: #beat to: #Executive gate: #beat: dFilter: [|#Source].
(12)
self link: #B gate: #beat to: #Executive gate: #beat: dFilter: [|#Source].
(13)
self link: #C gate: #beat to: #Executive gate: #beat: dFilter: [|#Source].Figure 5
Passive Replication topology management.
(a)
Initial topology
(b)
Topology after the removal of the faulty backup connectonB
(c)
Topology after the removal of the faulty principal connectonA.B becomes the principal connectonConnectonA plays the role of the primary replica andB andC play the role of backup replicas. External requests for position are sent to the executive gatexy. The executive determines the current time and sends a request for position through gatexy: that is only handled by the primary. ConnectonA computes the position at the current time and returns it to the executive. When the acceleration changes, the executive sends the new value through gatetime:ax:xy:. The primary computes a new position and updates state variables. It then sends the new state through gatebackup: so it can be stored in the passive replicas. As stated above, replicas are removed by the executive when they fail to send theheartbeat signal.There are two distinct failure cases that need to be handled differently. A fault detected in a backup replica is handled by simply removing that replica. The removal of a faulty backup unit is defined by Listing2. Since the removal operation also deletes all channels to and from the removed connecton, there is only a single command in this action.Listing 2:Removal of a faulty backup connecton.
(1)L
ocation>>removeBackup: aName
(2)self remove: aName.The removal of the primary replica needs to be handled differently since we need to promote one of the backups to become the primary. These changes in topology are defined by Listing3 where the new primary and the remaining replicas are sent as parameters.Listing 3:Removal of the faulty primary backup.
(1)L
ocation>>removePrimary: aName newPrimary: bName backups: aList
(2)self remove: aName.
(3)self link: #Executive gate: #time:ax:ay: to: bName gate: #time:ax:ay:.
(4)self link: #Executive gate: #xy: to: bName gate: #xy:.
(5)aList do: [:b|
(6) self link: bName gate: #backup: to: b gate: #state:.
(7)
.Once the faulty primary is removed, the executive is linked to the new primary through gatestime:ax:ay andxy:. The new primary gatebackup: is then linked to thestate: gates of the remaining backup replicas.


## 5. Active Replication

We consider now theActive Replication tactic to achieve fault tolerance. In this approach, several components are simultaneously active and can give an answer to any request. However, only the first answer, in the case of nonmalicious replicas, is taken into account, the others being ignored [9]. Contrarily to the Passive Replication, all replicas perform the same computations, this approach becoming more CPU intensive. This strategy is heavily dependent on the ability to establish group communication in a deterministic manner, since results are dependent on the order requests are made [9].Connectonsselect function can be used to establish the order of group communication. This function is implemented implicitly in Desmos that follows the order in which channels are declared in the structure definition.The ensemble of Figure6(a) represents an initial software topology for the Active Replication. ConnectonsA,B, andC play the same role in the active approach. Requests for position are sent to all the connectons in a deterministic order. This approach requires the asynchronous handling of replies since only one answer is required, since we consider here only the case of nonmalicious replicas. Thus, connectons do not give a direct answer but only answer an(id)entifier that is used to match callbacks that are sent through gatereply:id:. Callbacks are handled asynchronously, and the first reply to arrive to the executive is considered to be the answer. Later callbacks are ignored.Figure 6
Active Replication topology management.
(a)
Initial topology
(b)
Topology after the removal of the faulty connectonBFault detection is based on heartbeat, like in the previous section. Since all connectons are identical, their removal is described by Listing4, since no further distinction is required.Listing 4:Removal of the faulty connecton B.
(1)L
ocation>>removeActive: aName
(2)self remove: aName.The software topology becomes represented by Figure6(b) after the removal of the faulty connectonB.


## 6. N-Version Replication

We consider nowN-Version as a means of achieving resilience. N-Version uses different versions of software units with the same functional requirements [2] to obtain N-results for the same call. These results are then compared, and modules that have produced values considered to be wrong are treated as faulty and removed. A topology for N-Version is represented in Figure 7(a). The executive broadcasts the request for position to connectonsA,B, andC and waits for all the answers.Figure 7
N-Version software topology management.
(a)
Initial topology
(b)
Faulty connectonB is removed
(c)
ConnectonK replaces faulty software unitBWe consider hierarchical mobility [5], as a useful construct to replace faulty units. TheExecutive obtains the current position from all thePositionNV software units and tests if the returned values are within some tolerance limit. In case there are discrepancies, it finds and removes the faulty unit and sends it through gatefault:. A new unit arrives through gateupdate:name: bringing a replacement. Actually, any connecton compatible with thePositionNV model can be received. Given the hierarchical nature of connectons, an ensemble connecton can be used to replace a basic connecton, or vice versa. If we take, for example, software unitB as faulty, the ensemble becomes represented by Figure 7(b) after the removal ofB. The removal of a faulty unit is defined by Listing 5.Listing 5:Removal of a faulty connecton.
(1)L
ocation>>fault: aName
(2)|faulty|
(3)faulty:= self remove: aName.
“Removes connecton aName and all its channels”
(4)out fault: faulty.
“Sends faulty as a mobile connecton through the output gate fault:”Theremove: operation (Line 3) returns a software unit that can be handled as a regular object. This data is then sent through output gatefault: (Line 4), enabling hierarchical mobility. When aPositionNV replacement unit arrives, it is linked to the executive L
o
c
a
t
i
o
n
N
V
ϵ by the actionupdate:name: defined in Listing 6.Listing 6:Updating the faulty connecton.
(1)L
ocation>>update: aPosition name: aName
(2)aPosition state: (out state).
(3)self add: aPosition name: aName.
“Adds a mobile connecton”
(4)self link: #Executive gate: #time:ax:ay: to: aName gate: #time:ax:ay:.
(5)self link: #Executive gate: #xy: to: aName gate: #xy:.
(6)self link: #Executive gate: #state to: aName gate: #state rFilter: [:state|state % #Source].The executiveL
o
c
a
t
i
o
n
N
V
ϵ uses its output gatestate to retrieve the current state of the remaining connectons so the arriving one can be initialized. Since state information has a fixed format, it becomes crucial that the replacing mobile connecton understands that format. This is easy to achieve since state is known at the design time of the (mobile) connectons used to support fault tolerance. The ensemble of Figure 7(c) represents the correction achieved byPositionNV::K used to replace the faulty connectonPositionNV::B previously removed.As shown in this example, updates can use hierarchical mobility to introduce new versions of the software units. These updates do not require the detection of faults and can be motivated by the release of a more recent version of software. Hierarchical mobility provides, thus, a unifying construct to represent both software update and fault handling.


## 7. Comparison of the Replication Approaches and Related Work

We have presented a possible realization of three common replication approaches to fault-tolerance software. For simplicity, only one fault detection method was used in each tactic. Most common methods include exception handling, heartbeat (considered here), voting (used in the N-Version), and ping/echo [10]. These methods can be merged, and different implementations can require handling them in combination. We have considered the executive to perform most of the work. However, executive, functionally, can be broken in separate connectons. Some of the error handling could be used in a separate connecton, for example, so it could be reused in the different tactics.We do not foresee, however, advantages in the systematic partition of components intonormal andabnormal subcomponents [11, 12], since this decision seems to be domain dependent. In our case, faults (represented by the absence of the heartbeat message) are signaled to the executive that controls the structure, and no local treatment is required. In case of exceptions that can be handled locally, we consider that local methods can be a better choice, since they can use the local state in error correction. If handled by theabnormal component, faults would require the transmission of the local state. Requests dealing with faults that cannot be treated locally can be sent through an output gate toany external component that can handle it. The requirement for a mandatoryabnormal component seems thus excessive.We consider connectons as units of software reuse, and unless we have the evidence that a particularabnormal connecton can be used in different contexts, there is mostly no point in developing it.Tactics can be used in combination taking advantage of hierarchical composition. A unit used in N-Version can be implemented, for example, using the Active Replication approach. Since ensembles hide their internal structure, it will be transparent for the N-Version approach in which some or all of the units are implemented as a combination of connectons developed using different tactics.The initialPosition connecton described in Section 2.1 has suffered several changes so it could be used by the different tactics and fault detection mechanisms. This situation seems to indicate that it may be difficult to keep models and fault tolerance orthogonal. In our case, the nonfunctional requirement of resilience has become part of the models. The use of structural inheritance [3] can be employed to minimize the impact of transforming a base model into the several versions required by the different tactics for fault-tolerance detection and recovery.Hierarchical mobility can be used as an effective construct to replace software units or to make their update in any of the tactics described. This can be particularly useful for preventing future crashes. Bugs can be detected in some of the currently running components. After correction, these new versions can be put into production before they manifest in many other systems. This strategy is nowadays common and is used, for example, in the online update of antivirus and operating systems. Hierarchical mobility, however, provides a finer grain control over the components that need to be replaced.Hierarchical and modular principles have been used in many fields as a powerful heuristic for handling complex problems. One of the first formal descriptions of modular decomposition has been made in the area of General Systems Theory [13]. The decomposition of software in modules has latter been advocated in software engineering [14]. In this work, however, the hierarchical decomposition of software has not been introduced and the term hierarchy is simply used as synonymous of layered (software). We have extended General Systems Theory with dynamic topologies [15]. This work, however, could not be directly applied to software engineering since it is based on general systems asynchronous and unidirectional messages, making the specifications of software systems cumbersome.Software architectures have been developed to overcome the limitations of the object-oriented paradigm. Software components, as opposed to software objects, are intended to be built independently from the interconnections they may be part of, enabling a stronger form of reuse. A large variety of architecture definition languages have been developed but many are façades providing little support for developing a complete implementation of components and their interconnections [16–18].We have developed a system able to represent dynamic structure hierarchical and modular software that is fully compatible with the object-oriented style [3]. Other executable software architectures have also been proposed [19, 20], but they exhibit strong limitations, which makes these approaches incapable of providing the solutions presented here for replacing faulty software. In particular, ArchJava [19] requires an exact match of the gates so they can be connected. Additionally, links in ArchJava provide no filtering capabilities. ArchJava has limited capabilities to change software structure featuring no explicit operators to remove components or links. To the best of our knowledge,connecton is the only framework supporting hierarchical mobility [21–23].


## 8. Conclusions and Future Work

In this paper we propose an approach to fault-tolerant software based on modular software units.Connecton and its implementation in Desmos support the basic operators that enable dynamic changes in software topology. Most common fault-tolerant software approaches involve replication and the ability to remove faulty software. These basic constructs map easily into software topologies that, likeconnectons, supportad hoc changes in their structure. In particular, we have shown that Passive Replication, Active Replication, and N-Version programming can be easily modeled as dynamic structure software topologies. Hierarchical mobility has also been shown as an effective construct to update faulty software modules during runtime. Connectons are currently supported in a Java version [24]. Connectons/Java will be employed in the development of fault-tolerant software applications for real-world systems. Future work will also address the representation of the Active Replication approach in the presence of malicious replicas.



---

*Source: 321532-2015-06-16.xml*