The Cost of Scaling a Reliable Interconnection Topology

In distributed computing, many papers try to evaluate the message complexity of a distributed system as a function of the number of nodes n. But what about the cost of building the distributed system itself? Assuming that we want to reliably connect n nodes, how does the total number of nodes of the network evolve with n? Addressing such a question lies at the heart of achieving scalability in cloud computing. In this paper, we give the explicit description of a distributed system of which any two of the n nodes, for any n, remain connected (by a path of alive nodes and channels) with probability at least mu, despite the very fact that (a) every other node or channel has an independent probability lambda of failing, and (b) the number of channels connected to every node is physically bounded by a constant. We show however that if we also require any two of the n nodes to maintain a balanced message throughput with a constant probability, then O(nlog(1+epsilon) n) additional intermediary nodes are sufficient, where epsilon > 0 is an arbitrarily small constant.d