Diameter-Constrained Overlays with Faulty Links: Equilibrium, Stability, and Upper Bounds

In network overlays, virtual links among remote processes are usually established to circumvent the limitations of underlying protocols. The resulting dynamics have been recently studied, based on a novel random graph model that assumes that no link failure can occur. In that model, the case of faulty links has been only marginally stated to stimulate future research activities. Unfortunately, network overlays are very prone to faulty links, which are caused by any possible reasons, that force a node to loose its connectivity. To bridge this gap, this brief deepens the implications of faulty links in diameter-constrained overlays and demonstrates the following: 1) the resulting system has a unique globally stable equilibrium point; 2) the number of links composing the network is upper bounded in closed form; and 3) the speed of convergence to the equilibrium point is upper bounded in closed form, too. These outcomes grant for a stable regime and serve for estimating the overhead incurred by network nodes and sizing them adequately. Finally, to characterize the application bounds of the model, a stochastic analysis of its accuracy has been proposed, along with an extensive simulation campaign that encompasses a wide range of scenarios.