Traffic flows in a distributed computing network require both transmission and processing, and can be interdicted by removing either communication or computation resources. We study the robustness of a distributed computing network under the failures of communication links and computation nodes. We define cut metrics that measure the connectivity, and show a non-zero gap between the maximum flow and the minimum cut. Moreover, we study a network flow interdiction problem that minimizes the maximum flow by removing communication and computation resources within a given budget. We develop mathematical programs to compute the optimal interdiction, and polynomial-time approximation algorithms that achieve near-optimal interdiction in simulation.
翻译:分布式计算网络的流量既需要传输和处理,也可以通过删除通信或计算资源来截断。我们研究了通信链路和计算节点的故障下分布式计算网络的稳健性。我们定义了测量连接的削减尺度,并显示了最大流量和最小削减之间的非零差距。此外,我们研究了一个网络流量阻截问题,通过在特定预算内删除通信和计算资源,最大限度地减少最大流量。我们开发了计算最佳阻截的数学程序,以及在模拟中实现接近最佳阻截的多元时近算法。