Next: Introduction.
Designing Computer Networks to Avoid Partitioning
Patrick E. O'Neil
-
Kenneth Baclawski
-
D. Frank Hsu
Abstract:
It is shown that a network can be constructed on a given set of host computers
such that the possibility of a network partition resulting from network node
and link failure can be ruled out with an arbitrarily high degree of
confidence.
More precisely, a class of networks is exhibited on any given number of host
nodes so that the probability of a network partition decreases exponentially
with only a linear increase in 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 choice of network topology.
This paper makes this intuitive statement precise and analyzes one class of
networks to illustrate it:
bipartite networks where host nodes are connected
to each of a set of hub nodes.
The result has significant implications for
availability of distributed databases and feasibility of the three-phase
commit protocol which guarantees crash recovery in distributed transactions.
Kenneth Baclawski
Wed Nov 1 21:08:51 EST 1995