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
Sep 01 2020

Note: The status of this file is: Anyone

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

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)