# Presentation: 036327

## Deploying Analytical Redundancyfor System Fault Tolerance

- V. Cortellessa, D. Del Gobbo, A. Mili, M. Shereshevsky, and Z. Zhuang
- CSEE Dept. West Virginia University - Morgantown

- FY2001 University Software Initiative for the NASA IV&V Facility - Fairmont WV

## Outline

- Characterizing Redundancy
- Quantifying Redundancy
- Qualifying Redundancy

## CHARACTERIZING REDUNDANCY

## Objectives

- To develop a classification of redundancy by identifying the orthogonal dimensions in redundancy
- To analyze physical and analytical redundancy on the basis of the obtained classification
- To answer general questions about redundancy:
- What is redundancy?
- Can we talk about redundancy outside the context of fault tolerance?
- Can we distinguish between intrinsic redundancy and redundancy-by-design?
- Is redundancy a representation issue or a design issue?
- Is physical redundancy an extreme case of redundancy?

## Definition of Redundancy

- From *IEEE Dictionary*
- _duplication_ of elements for the purpose of enhancing system reliability
- presence of _auxiliary_ components in a system for the purpose of preventing or recovering from failures
- the existence of _more than one means_ for performing a given _function_
- pertaining to characters that _do not contribute_ to the information content
- Log (# symbols) - average information content per symbol

## Definition of RedundancyFunctional vs. State Redundancy

- State redundancy
- system state *[x**0**, x**1**, ... x**n**]* *(implementation dependent)*
- Functional redundancy
- System level requirements *R={(u,y)| ...}*
- Subsystem/component level requirements *R={(x**i**, x**j**)|...}* *(implementation dependent)*

## Content Redundancy English language sentence (Shannon)

- No redundancy
- symbols are independent and equiprobable
- First-level redundancy
- symbols are independent but with frequency of English text
- digram structure as in English text
- trigram structure as in English text
- Word redundancy
- words are independent but with frequency of English text
- word transition probability is that of English text

## Content Redundancy Physical system

- Rigid body in free fall ( *p, v, a, F, M)*
- No redundancy
- quantities are independent and each uniformly distributed
- Local redundancy (quantities are still independent)
- each quantity is assigned a probability distribution
- relationship among each quantity at different time instants
- System redundancy
- instantaneous dependency between different quantities
- temporal dependency between different quantities

## Representation RedundancyParity-bit

- Information in order to be processed needs to be represented in some suitable manner
- The *parity-bit* in serial communication allows detecting non-admissible strings of  bits.
- Admissibility of the string of bits is independent of the information content

## Temporal/Sequential Redundancy

- Some applications are characterized by a sequential introduction of data
- Shannon’s example
- first-order redundancy is a single-step redundancy
- following orders of redundancy are multiple-step
- Physical system example
*F(t**i**) = M(t**i**)a(t**i**)*  is single-step (instantaneous) redundancy
*v(t**2**) = [p(t**2**)-p(t**1**)]/(t**2**-t**1**) *is multiple-step (temporal) redundancy

## Analytical Redundancy

- _System/Subsystem_/component level functional redundancy
- State redundancy
- Content redundancy
- Representation redundancy
- Single/_multiple-step_ redundancy

## Physical Redundancy

- _Component_ level functional redundancy
- State redundancy
- Content redundancy
- Representation redundancy
- _Single-step_ redundancy (deterministic asset)

## QUANTIFYING REDUNDANCY

## Objectives

- To quantify the amount of redundancy by means of a numeric function
- To characterize analytical vs physical redundancy by means of this function
- To characterize Fault Tolerance Capabilities (e.g., detection, identification, etc.) by means of this function
- Use this function to support decision making in redundancy vs Fault Tolerant Capability tradeoffs

## Redundancy as the ability to choose among representations

- X : system state
- P : set of all the “possible” system states
- C : set of all the “correct” system states

*Prob* ( X  C  | X  P )

- The corresponding ***conditional entropy*** is a suitable metric of “how fully the potential domain is being exploited” (or, conversely, how sparsely populated it is), i.e. how much redundancy the system shows in terms of unused possible states

## Redundancy as logical relation among state variables

-  State made up of two (aggregate of) variables, say X and Y
-  P(X|Y) : to what extent the value of Y determines the values of X
-  H(X|Y) : Amount of uncertainty that remains about X if we know Y
- H(X|Y) = H(X,Y) – H(Y)

## A simple example

- a: *system variable*

*SYSTEM*

-  : *vector of readings of *a

*Hypothesis*: there is redundancy only if  uniquely determines a

- H(a | ) = 0    ( = H(a , ) – H() )

- a

- 

- f

-  a : P(f -1(a)) = P(a)

## This property holds: 

- 			H(a)  H()
- 	and the distance depends on the injectivity of f
- 	(e.g., one-to-one mapping gives H(a) = H() )

- Again we may consider, as a measure of redundancy:
- 		 () = H() - H(a)  ( = H( | a) )
- i.e., how fully the potential domain of  values is being exploited.

## We voluntarily omit a as a parameter of  because:

- We voluntarily omit a as a parameter of  because:

-  P(a) comes from the intrinsic system operational profile (there is no control on it)
- 			while
-  P() is the result of design choices and fault hypotheses (its value can be controlled by design)

## QUALIFYING REDUNDANCY

## Objectives

- Whereas the previous section quantifies redundancy, this section qualifies it. The same amount of redundancy may or may not be useful, depending on functional properties
- Whereas in quantifying redundancy we need to distinguish between correct and representable (possible) states, in this section we will distinguish between:
- Correct states
- Maskable states
- Recoverable states
- Representable states

## Notation

-  s0 : system initial state
- milestone: breaking point between past and future behavior of the system
-  : relation that describes the past behavior
-  : relation that describes the future behavior
-  : system requirements

## s0

- s0

- 

- 

- 

- (s0)

*milestone*

**s ***is a ****correct**** state:*** **

- (s0,**s**)  

-    (s0)

## s0

- s0

- 

- 

- 

- (s0)

- maskable

*milestone*

- (s0,**s**)  K (, )

**s ***is a ****maskable**** state:*** **

-    (s0)

## 

- 

- 

- (s0)

- maskable

- ’

- r

*milestone*

**s ***is a ****recoverable ****state***:**

- s0

- r : ’   r       K (, )

-    (s0)

## Question

- For what ’ and K this equation has a solution?
_*Analogy*_: for what a,b does the equation ax=b have a solution?
_*Answer*_: a0

- r : ’   r       K (, )

## Answer: conditions for existence of r

- - C1 -    K L  ’ L
- - C2 -    (K L  ’)^ K       *must be a total relation*

- In practice, we look for the ***smallest*** ’ s.t. C1 and C2 hold
- (i.e., the relation that maps initial to recoverable states only)

- - C1 -    K L = ’ L

- - C2 -    ’ K       *must be a total relation*

## A sufficient condition for C2

- If the domain partition determined by K is preserved by ’
- then condition C2  holds

- ’ ’   K K

- 

- ’ K       *is a total relation*

_*A simple example*_

**K = { (s,s’) | s’ = s mod 6}**

- ’1** = { (s,s’) | s’ = s mod 12}**

- ’2** = { (s,s’) | s’ = (s+5) mod 18}**

**Only produces**
**recoverable states**

- recovery: **s’ = s mod 6**

**Only produces**
**recoverable states**

- recovery: **s’ = (s+1) mod 6**

- ’3** = { (s,s’) | s’ = s mod 10}**

**It does not produce**
**recoverable states**

## Conclusions and Future Work

- We have developed a framework for reasoning about redundancy
- It includes: Classification/Quantification/Qualification
- Future work
- Refining/reorganizing classification
- Evaluate quantification
- Validate qualification