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.


翻译:分布式计算网络的流量既需要传输和处理,也可以通过删除通信或计算资源来截断。我们研究了通信链路和计算节点的故障下分布式计算网络的稳健性。我们定义了测量连接的削减尺度,并显示了最大流量和最小削减之间的非零差距。此外,我们研究了一个网络流量阻截问题,通过在特定预算内删除通信和计算资源,最大限度地减少最大流量。我们开发了计算最佳阻截的数学程序,以及在模拟中实现接近最佳阻截的多元时近算法。

0
下载
关闭预览

相关内容

DC:Distributed Computing。 Explanation:分布式计算。 Publisher:Springer。 SIT:http://dblp.uni-trier.de/db/journals/dc/
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
4+阅读 · 2019年1月14日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
CCF推荐 | 国际会议信息10条
Call4Papers
8+阅读 · 2019年5月27日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
计算机类 | SIGMETRICS 2019等国际会议信息7条
Call4Papers
9+阅读 · 2018年10月23日
CCF B类期刊IPM专刊截稿信息1条
Call4Papers
3+阅读 · 2018年10月11日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Top
微信扫码咨询专知VIP会员