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
08375657.pdf
openaccess
1.42 MB
Adobe PDF
f3c0541b0d212d14a641eafdfd0cda28