Tight Bounds for Selfish and Greedy Load Balancing
Tight Bounds for Selfish and Greedy Load Balancing
复制标题
自私和贪婪负载平衡的严格界限
作者：
I. Caragiannis;M. Flammini;C. Kaklamanis;P. Kanellopoulos;L. Moscardelli
我们在一组客户端的上下文中研究负载平衡问题，每个客户端都希望在从特定客户端允许的服务器子集中选择的服务器上运行作业。我们考虑两种不同的情况。在自私负载平衡中，每个客户端是自私的，因为它在其可允许的服务器中选择在具有最小延迟的服务器上运行其作业，给定其他客户端的作业到服务器的分配。在在线负载平衡中，客户端在线出现，当客户端出现时，它必须做出不可撤销的决定，并将其作业分配给其允许的服务器之一。在这里，我们假设客户端的目标是优化一些全球标准，但在一个在线的时尚。每个客户端在做出决定时可以使用的自然局部优化标准是将其作业分配给给出全局目标的最小增加的服务器。这导致了贪婪的在线解决方案。本文的目的是确定自私和贪婪对负载平衡质量的影响程度。我们通过提出新的和改进的，紧或几乎紧的界限上的价格无政府状态的自私的负载平衡，以及竞争力的贪婪算法的在线负载平衡时，目标是最小化的总具有线性延迟功能的服务器上所有客户端的延迟。此外，我们证明了一个紧的上界的价格稳定的线性拥塞游戏。
We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness.We characterize almost completely the impact of selfishness and greediness in load balancing by presenting new and improved, tight or almost tight bounds on the price of anarchy of selfish load balancing as well as on the competitiveness of the greedy algorithm for online load balancing when the objective is to minimize the total latency of all clients on servers with linear latency functions. In addition, we prove a tight upper bound on the price of stability of linear congestion games.