New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

Network delay-aware load balancing in selfish and cooperative distributed systems

SpeakerPiotr Skowron

When accessing remote services, the observed latency is a sum of communication delays and the time needed to handle the request on a server. The handling time depends on the server congestion, i.e. the total number of requests a server must handle. We analyze the problem of balancing the divisible load in a network of servers in order to minimize the total observed latency. We consider both cooperative and selfish servers (each server aiming to minimize the latency of the locally-produced requests). The problem can be generalized to the task scheduling in a distributed cloud; or to content delivery in an organizationally-distributed CDNs. In a cooperative network, we show that the problem is polynomially solvable. We also present a distributed algorithm iteratively balancing the load. We prove that the distributed algorithm converges; moreover, we show how to estimate the distance between the current solution and the optimum based on the amount of load exchanged by the algorithm. During the experimental evaluation, we show that the distributed algorithm is efficient, therefore it can be used in networks with dynamically changing loads. In a network of selfish servers, we prove that the price of anarchy (the loss of performance due to selfishness) is low when the network is homogeneous and the servers are loaded (the request handling time is high compared to the communication delay). After relaxing these assumptions, we assess the price of anarchy experimentally, showing that it remains low. Our results indicate that a network of servers handling requests can be efficiently managed by a distributed algorithm. Additionally, even if the network is organizationally distributed, with individual servers optimizing performance of their requests, the network remains efficient.