From: cme@ellisun.sw.stratus.com (Carl Ellison)
Date: Sat, 23 Oct 93 15:58:28 PDT
To: cypherpunks@toad.com
Subject: Re:  Emergency Broadcast System
Message-ID: <9310232257.AA04098@ellisun.sw.stratus.com>
MIME-Version: 1.0
Content-Type: text/plain


>Message-Id: <9310221941.AA16004@toad.com>
>Subject: Emergency Broadcast System
>Date: Fri, 22 Oct 1993 13:36:33 -0600 (MDT)
>From: "Philippe_D_Nave" <pdn@dwroll.dw.att.com>


> 1) Mailing list data should be distributed to "N" sites where "N" is a 
>    magic number that minimizes the chance of losing all the copies.
>    (Mathematicians, sharpen your pencils!)

I found the equations I mentioned earlier.  The following is a latex
file giving some.  The trend should be obvious.  You don't need many
nodes, if you can repair broken ones quickly enough.

[This is why Stratus has such a large FedEx bill.  When one of our machines
gets a broken component, it phones home automatically, reports the failure
and a new part is FedEx'ed immediately.  If the report comes in by
midnight, the new part is on the customer's desk for him/her to replace by
9am.  (Our current machines have N=2, K=1).  We prefer high speed mailaing
of parts (from a warehouse at FedEx's central sorting airport) over normal
mail in order to maximize $\mu$.]

------------------------------------------------------------------------------

\documentstyle[12pt]{article}

\begin{document}

\title{MTTF of Various Systems}
\author{Carl M. Ellison \thanks{Stratus Computer Inc., 55 Fairbanks Blvd.,
Marlborough MA 01752. Email address: {\tt cme@sw.stratus.com}.}}
\date{June 18, 1993}

\maketitle

\begin{abstract}
Equations are presented for the Mean Time To Failure (MTTF)
of various systems, as a function of
the number of nodes in the system, N, and the minimum number of nodes
in a working system, K.  Failure of a system is defined as having fewer
than K working nodes.
\end{abstract}

\section{Equations} 

Here are some equations for the Mean Time To Failure (MTTF) of various
systems, as a function of the number of nodes in the system, N, and
the minimum number of nodes in a working system, K.  Failure of a
system is defined as having fewer than K working nodes.  Typically,
K=1 and each node has a complete copy of each database.  However,
sometimes the data can be kept on multple nodes (as in a RAID-5 disk
array) which will tolerate some failures, down to a given threshold.

It is assumed that as soon as a failure occurs, a repair cycle will be
started.  There is then a race to see if the repair can be completed
before enough additional nodes fail to drop the working number below
K.  If that race is lost, it is assumed that information has been lost,
in the worst case, but at least that the service represented by the N nodes
is not available.

These equations do not give system availability (probability that a service
is available) but rather MTTF.  Availability equations can be found in
several good textbooks.  See, for example, Trivedi's text on Statistics.
MTTF is more difficult to compute.

The equations below were each a symbolic solution to a custom Markov
chain, built to model the choice of N and K.


N: number of nodes in a full system

K: number of nodes in a minimally functional system

$\lambda$: rate of failures (e.g., number of node failures per year)

$\mu$: rate of node repair (in the same units as $\lambda$)

Each fraction below is the MTTF of the whole system:  the mean time
until a system drops to only (K-1) working nodes.

N =  3 ;  K =  2

\begin{equation}
\frac{ 5\lambda + \mu }{ 6\lambda^2 }
\end{equation}

N =  4 ;  K =  2

\begin{equation}
\frac{ 26\lambda^2 + 6\lambda\mu + \mu^2 }{ 24\lambda^3 }
\end{equation}

N =  4 ;  K =  3

\begin{equation}
\frac{ 7\lambda + \mu }{ 12\lambda^2 }
\end{equation}

N =  5 ;  K =  2

\begin{equation}
\frac{ 154\lambda^3 + 36\lambda^2\mu + 7\lambda\mu^2 + \mu^3 }{ 120\lambda^4 }
\end{equation}

N =  5 ;  K =  3

\begin{equation}
\frac{ 47\lambda^2 + 8\lambda\mu + \mu^2 }{ 60\lambda^3 }
\end{equation}

N =  5 ;  K =  4

\begin{equation}
\frac{ 9\lambda + \mu }{ 20\lambda^2 }
\end{equation}

N =  6 ;  K =  2

\begin{equation}
\frac{ 1044\lambda^4 + 240\lambda^3\mu + 48\lambda^2\mu^2 + 8\lambda\mu^3 + \mu^4 }{ 720\lambda^5 }
\end{equation}

N =  6 ;  K =  3

\begin{equation}
\frac{ 342\lambda^3 + 60\lambda^2\mu + 9\lambda\mu^2 + \mu^3 }{ 360\lambda^4 }
\end{equation}

N =  6 ;  K =  4

\begin{equation}
\frac{ 74\lambda^2 + 10\lambda\mu + \mu^2 }{ 120\lambda^3 }
\end{equation}

N =  6 ;  K =  5

\begin{equation}
\frac{ 11\lambda + \mu }{ 30\lambda^2 }
\end{equation}

N =  7 ;  K =  2

\begin{equation}
\frac{ 8028\lambda^5 + 1800\lambda^4\mu + 360\lambda^3\mu^2 + 62\lambda^2\mu^3 + 9\lambda\mu^4 + \mu^5 }{ 5040\lambda^6 }
\end{equation}

N =  7 ;  K =  3

\begin{equation}
\frac{ 2754\lambda^4 + 480\lambda^3\mu + 75\lambda^2\mu^2 + 10\lambda\mu^3 + \mu^4 }{ 2520\lambda^5 }
\end{equation}

N =  7 ;  K =  4

\begin{equation}
\frac{ 638\lambda^3 + 90\lambda^2\mu + 11\lambda\mu^2 + \mu^3 }{ 840\lambda^4 }
\end{equation}

N =  7 ;  K =  5

\begin{equation}
\frac{ 107\lambda^2 + 12\lambda\mu + \mu^2 }{ 210\lambda^3 }
\end{equation}

N =  7 ;  K =  6

\begin{equation}
\frac{ 13\lambda + \mu }{ 42\lambda^2 }
\end{equation}

N =  8 ;  K =  2

\begin{equation}
\frac{ 69264\lambda^6 + 15120\lambda^5\mu + 3000\lambda^4\mu^2 + 520\lambda^3\mu^3 + 78\lambda^2\mu^4 + 10\lambda\mu^5
+ \mu^6 }{ 40320\lambda^7 }
\end{equation}

N =  8 ;  K =  3

\begin{equation}
\frac{ 24552\lambda^5 + 4200\lambda^4\mu + 660\lambda^3\mu^2 + 92\lambda^2\mu^3 + 11\lambda\mu^4 + \mu^5 }{ 20160\lambda^6 }
\end{equation}

N =  8 ;  K =  4

\begin{equation}
\frac{ 5944\lambda^4 + 840\lambda^3\mu + 108\lambda^2\mu^2 + 12\lambda\mu^3 + \mu^4 }{ 6720\lambda^5 }
\end{equation}

N =  8 ;  K =  5

\begin{equation}
\frac{ 1066\lambda^3 + 126\lambda^2\mu + 13\lambda\mu^2 + \mu^3 }{ 1680\lambda^4 }
\end{equation}

N =  8 ;  K =  6

\begin{equation}
\frac{ 146\lambda^2 + 14\lambda\mu + \mu^2 }{ 336\lambda^3 }
\end{equation}

N =  8 ;  K =  7

\begin{equation}
\frac{ 15\lambda + \mu }{ 56\lambda^2 }
\end{equation}

N =  9 ;  K =  3

\begin{equation}
\frac{ 241128\lambda^6 + 40320\lambda^5\mu + 6300\lambda^4\mu^2 + 888\lambda^3\mu^3 + 111\lambda^2\mu^4
+ 12\lambda\mu^5 + \mu^6 }{ 181440\lambda^7 }
\end{equation}

N =  9 ;  K =  4

\begin{equation}
\frac{ 60216\lambda^5 + 8400\lambda^4\mu + 1092\lambda^3\mu^2 + 128\lambda^2\mu^3 + 13\lambda\mu^4 + \mu^5 }{ 60480\lambda^6 }
\end{equation}

N =  9 ;  K =  5

\begin{equation}
\frac{ 11274\lambda^4 + 1344\lambda^3\mu + 147\lambda^2\mu^2 + 14\lambda\mu^3 + \mu^4 }{ 15120\lambda^5 }
\end{equation}

N =  9 ;  K =  6

\begin{equation}
\frac{ 1650\lambda^3 + 168\lambda^2\mu + 15\lambda\mu^2 + \mu^3 }{ 3024\lambda^4 }
\end{equation}

N =  9 ;  K =  7

\begin{equation}
\frac{ 191\lambda^2 + 16\lambda\mu + \mu^2 }{ 504\lambda^3 }
\end{equation}

N =  9 ;  K =  8

\begin{equation}
\frac{ 17\lambda + \mu }{ 72\lambda^2 }
\end{equation}

N = 10 ;  K =  4

\begin{equation}
\frac{ 662640\lambda^6 + 90720\lambda^5\mu + 11760\lambda^4\mu^2 + 1400\lambda^3\mu^3 + 150\lambda^2\mu^4
+ 14\lambda\mu^5 + \mu^6 }{ 604800\lambda^7 }
\end{equation}

N = 10 ;  K =  5

\begin{equation}
\frac{ 127860\lambda^5 + 15120\lambda^4\mu + 1680\lambda^3\mu^2 + 170\lambda^2\mu^3 + 15\lambda\mu^4 + \mu^5 }{ 151200\lambda^6 }
\end{equation}

N = 10 ;  K =  6

\begin{equation}
\frac{ 19524\lambda^4 + 2016\lambda^3\mu + 192\lambda^2\mu^2 + 16\lambda\mu^3 + \mu^4 }{ 30240\lambda^5 }
\end{equation}

N = 10 ;  K =  7

\begin{equation}
\frac{ 2414\lambda^3 + 216\lambda^2\mu + 17\lambda\mu^2 + \mu^3 }{ 5040\lambda^4 }
\end{equation}

N = 10 ;  K =  8

\begin{equation}
\frac{ 242\lambda^2 + 18\lambda\mu + \mu^2 }{ 720\lambda^3 }
\end{equation}

N = 10 ;  K =  9

\begin{equation}
\frac{ 19\lambda + \mu }{ 90\lambda^2 }
\end{equation}

\end{document}