##
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

Published in:

Ieee Transactions On Dependable And Secure Computing, 17, 5, 1039-1050

ISSN:

1545-5971

1941-0018

Keywords:

Laboratories:

**Note: **The status of this file is: Anyone

Record created 2020-09-09, last modified 2020-10-29