We now give a general asymptotic result for the probability of network partitioning. The concept of d-diameter is important for computing this probability.
Proof. The event that N is partitioned is the union of the events
, the union being taken over all distinct pairs
, where 
represents the following event:
``The vertices 
and 
are in service, and there is no path
joining 
and 
via vertices and edges that are in service.''
Let 
and 
be any two distinct vertices. Since N is d-
connected, there are d vertex-disjoint paths joining 
and
. By definition of the d-diameter, one can choose these paths so
that the longest one has length at most k. If the event 
is true, then some node or link is out of service on every one of these
paths. By stochastic independence, 
, where
. Therefore 
. The result follows. height 8pt width 4.5pt depth 1pt
In practice, the probability p is very small. So the asymptotic term in the theorem can be neglected. The result therefore states that the probability of partitioning decreases exponentially with the connectivity of the network, provided that the d-diameter can be controlled.
The complete graph or fully connected network is an example of a
highly-connected network with low d-diameter.
If a fully connected network has n nodes, then it is 
-connected and
has 
-diameter 2.
As n increases, the probability of partition of this network decreases
exponentially in n.
Unfortunately, the ``cost'' of this network increases quadratically with the
number of nodes since there are 
links in a fully connected
network.
We would like to show that one can design the network so that the probability
of network partition decreases exponentially with only a linear cost.
Somewhat more precisely, for any given number n of nodes, we would like to
find a class of networks on these nodes parameterized by a parameter x such
that
for some constant 
.
In this design aim, the constant 
is proportional to the number of nodes
n, which is arbitrary but held constant while x increases. In the next
section, we introduce a class of networks that has this property.