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)$。我们的两个结果依赖于不同的算法和技术,因此具有独立的利益。