It is shown that a network can be constructed on a given set of host c
omputers such that the possibility of a network partition resulting fr
om network node and link failure can be ruled out with an arbitrarily
high degree of confidence. More precisely, a class of networks is exhi
bited on any given number of host nodes so that the probability of a n
etwork partition decreases exponentially with only a linear increase i
n connectivity cost. It has long been a folk theorem in network theory
that as one increases the budget for the number of links of a network
, the reliability of the network can be increased by a judicious choic
e of network topology. This paper makes this intuitive statement preci
se and analyzes one class of networks to illustrate it: bipartite netw
orks where host nodes are connected to each of a set of hub nodes. The
result has significant implications for availability of distributed d
atabases and feasibility of the three-phase commit protocol which guar
antees crash recovery in distributed transactions.