The performance of many large-scale and data-intensive distributed systems critically depends on the capacity of the interconnecting network. This paper is motivated by the vision of self-adjusting infrastructures whose resources can be adjusted according to the workload they currently serve, in a demand-aware manner. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by dynamically moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter rack. In particular, we revisit the online balanced graph partitioning problem which captures the fundamental tradeoff between the benefits and costs of dynamically collocating communication partners. The demand is modelled as a sequence $\sigma$ (revealed in an online manner) of communication requests between $n$ processes, each of which is running on one of the $\ell$ servers. Each server has capacity $k=n/\ell$, hence, the processes have to be scheduled in a balanced manner across the servers. A request incurs cost $1$, if the requested processes are located on different servers, otherwise the cost is 0. A process can be migrated to a different server at cost $1$. This paper presents the first online algorithm for online balanced graph partitioning achieving a polylogarithmic competitive ratio for the fundamental case of ring communication patterns. Specifically, our main contribution is a $O(\log^3 n)$-competitive randomized online algorithm for this problem. We further present a randomized online algorithm which is $O(\log^2 n)$-competitive when compared to a static optimal solution. Our two results rely on different algorithms and techniques and hence are of independent interest.


翻译:很多大规模和数据密集型分布式系统的性能取决于互连网络的容量。本文的动机是实现自适应基础设施的愿景,这些基础设施的资源可以根据它们目前服务的工作负载进行调整,以需求感知的方式。这样的动态调整可以通过将频繁交互的通信伙伴动态地移动到更靠近的位置来提高网络利用率和性能,例如,将它们放在同一台服务器或数据中心机架中。特别地,我们重新审视了在线平衡图分割问题,它捕捉到动态放置通信伙伴的效益和成本之间的基本权衡。需求被建模为一个通信请求序列 $\sigma$(以在线方式逐步披露),其中 $n$ 个进程中的每个进程都在 $\ell$ 个服务器之一上运行。每个服务器的容量为 $k=n/\ell$,因此,必须在服务器之间平衡地调度进程。如果所请求的进程位于不同的服务器上,则请求会产生成本 $1$,否则成本为 $0$。可以以成本 $1$ 将进程迁移到不同的服务器上。本文提出了第一个在线算法,解决了在线平衡图分割问题,实现了多对数竞争比,针对环形通信模式的基本情况。具体而言,我们的主要贡献是一种 $O(\log^3 n)$-competitive 的随机在线算法。在与 static 最优解进行比较时,我们进一步提出了一种随机在线算法,其竞争比为 $O(\log^2 n)$。我们的两个结果依赖于不同的算法和技术,因此具有独立的利益。

0
下载
关闭预览

相关内容

【2022新书】高效深度学习,Efficient Deep Learning Book
专知会员服务
117+阅读 · 2022年4月21日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年6月1日
VIP会员
相关VIP内容
【2022新书】高效深度学习,Efficient Deep Learning Book
专知会员服务
117+阅读 · 2022年4月21日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
【泡泡汇总】CVPR2019 SLAM Paperlist
泡泡机器人SLAM
14+阅读 · 2019年6月12日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员