In this paper, we present algorithms for designing networks that are robust to node failures with minimal or limited number of links. We present algorithms for both the static network setting and the dynamic network setting; setting where new nodes can arrive in the future. For the static setting, we present algorithms for constructing the optimal network in terms of the number of links used for a given node size and the number of nodes that can fail. We then consider the dynamic setting where it is disruptive to remove any of the older links. For this setting, we present online algorithms for two cases: (i) when the number of nodes that can fail remains constant and (ii) when only the proportion of the nodes that can fail remains constant. We show that the proposed algorithm for the first case saves nearly $3/4$th of the total possible links at any point of time. We then present algorithms for various levels of the fraction of the nodes that can fail and characterize their link usage. We show that when $1/2$ the number of nodes can fail at any point of time, the proposed algorithm saves nearly $1/2$ of the total possible links at any point of time. We show that when the number of nodes that can fail is limited to the fraction $1/(2m)$ ($m \in \mathbb{N}$), the proposed algorithm saves nearly as much as $(1-1/2m)$ of the total possible links at any point of time. We also show that when the number of nodes that can fail at any point of time is $1/2$ of the number of nodes plus $n$, $n \in \mathbb{N}$, the number of links saved by the proposed algorithm reduces only linearly in $n$. We conjecture that the saving ratio achieved by the algorithms we present is optimal for the dynamic setting.
翻译:在本文中, 我们提出设计网络的算法, 这些网络在节点失败时非常强, 连接数量很少或有限。 我们为以下两种情况提供在线算法:(一) 能够失败的节点数量保持不变, 并且(二) 只有节点的比例仍然不变。 对于静点大小和节点数量可以在未来到达。 对于静点设置, 我们提出构建最佳网络的算法, 以用于给定节点大小的链接数量和可能失败的节点数量为基础。 然后我们提出能够取消任何旧链接的动态设置。 对于这一设置, 我们为两个案例提供在线算法:(一) 能够失败的节点数量保持不变, 并且(二) 只有节点数量不变的节点数量保持不变, 并且(二) 只有节点的节点比例的比例保持不变。 我们显示第一个例的拟议算算法在任何一个时候可以节省近1/2美元的总链接的总额, 也就是说, 美元% 的节点在任何时间里, 我们可能实现的节点的节点将减少。