DESIGNING COMPUTER-NETWORKS TO AVOID PARTITIONING

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.