There is a continuity of scheduling models describing shared supercomputing systems. Classic approaches model the problem as singleobjective optimization; the objective corresponds to optimizing the performance of the system (the makespan, or the sum of jobs' completion times). Multiobjective methods assign an objective to each agent in the systembe it the end user, or an organization. Finally, gametheoretic methods model possible actions of the agents, be it a strategic change in the job parameters to try to get to the beginning of the queue, or a coalition of organizations deciding to isolate themselves from the rest of the system.
gametheoretic resource management and scheduling
 Piotr Skowron and Krzysztof Rzadca.
Nonmonetary fair scheduling  a cooperative game theory approach.
In SPAA 2013, 25th ACM Symposium on Parallelism in
Algorithms and Architectures, 2013.
[ bib 
http 
.pdf ]
We consider a multiorganizational system in which each organization contributes processors to the global pool but also jobs to be processed on the common resources. The fairness of the scheduling algorithm is essential for the stability and even for the existence of such systems (as organizations may refuse to join an unfair system).
We consider online, nonclairvoyant scheduling of sequential jobs. The started jobs cannot be stopped, canceled, preempted, or moved to other processors. We consider identical processors, but most of our results can be extended to related or unrelated processors.
We model the fair scheduling problem as a cooperative game and we use the Shapley value to determine the ideal fair schedule. In contrast to the current literature, we do not use money to assess the relative utilities of jobs. Instead, to calculate the contribution of an organization, we determine how the presence of this organization influences the performance of other organizations. Our approach can be used with arbitrary utility function (e.g., flow time, tardiness, resource utilization), but we argue that the utility function should be strategy resilient. The organizations should be discouraged from splitting, merging or delaying their jobs. We present the unique (to within a multiplicative and additive constants) strategy resilient utility function.
We show that the problem of fair scheduling is NPhard and hard to approximate. However, for unitsize jobs, we present a fully polynomialtime randomized approximation scheme (FPRAS). We also show that the problem parametrized with the number of organizations is fixed parameter tractable (FPT). In cooperative game theory, the Shapley value is considered in many contexts as “the” fair solution. Our results show that, although the problem for the large number of organizations is computationally hard, this solution concept can be used in scheduling (for instance, as a benchmark for measuring fairness of heuristic algorithms).
 Piotr Skowron and Krzysztof Rzadca.
Fair share is not enough: measuring fairness in scheduling with
cooperative game theory.
In PPAM 2013, International Conference on Parallel
Processing and Applied Mathematics, LNCS. Springer, 2013.
[ bib 
.pdf ]
We consider the problem of fair scheduling in a multiorganizational system in which organizations are contributing their own resources to the global pool and the jobs to be processed on the common resources. We consider online, nonclairvoyant scheduling of sequential jobs without preemption. The organizations must agree on the order of executing the jobs, i.e. on the scheduling algorithm. To ensure that the organizations are willing to cooperate the scheduling algorithm must be fair.
To characterize fairness, we use cooperative game theory approach. The contribution of an organization is computed based on how this organization influences the utility (which can be any metric, e.g., flow time, turnaround, resource allocation, etc.) of all organizations. Formally, the contribution of the organization is its Shapley value in the cooperative game. The scheduling algorithm should ensure that the contributions of the organizations are close to their utilities. Our previous work proves that this problem is NPhard and hard to approximate.
In this paper we propose a heuristic scheduling algorithm for the fair scheduling problem. We experimentally evaluate the heuristic and compare its fairness to other algorithms (fair share, round robin) and the exact exponential algorithm. Our results show that fairness of the heuristic algorithm is close to the optimal. The difference between our heuristic and the fair share algorithm is more visible on longer traces with more organizations. We believe that these results prove that fair share might not be an optimal solution for multiorganizational systems.
 Piotr Skowron and Krzysztof Rzadca.
Network delayaware load balancing in selfish and cooperative
distributed systems.
In HCW 2013, 22st International Heterogeneity in
Computing Workshop (in conjunction with IPDPS 2013), 2013.
[ bib 
http 
.pdf ]
We consider a geographically distributed request processing system composed of various organizations and their servers connected by the Internet. The latency a user observes 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 load in a network of servers in order to minimize the total observed latency. We consider both cooperative and selfish organizations (each organization aiming to minimize the latency of the locallyproduced requests). The problem can be generalized to the task scheduling in a distributed cloud; or to content delivery in an organizationallydistributed CDNs.
In a cooperative network, we show that the problem is polynomially solvable. We also present a distributed algorithm iteratively balancing the load. 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 organizations, we prove that the price of anarchy (the worstcase 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 loss of performance caused by the selfishness experimentally, showing that it remains low.
Our results indicate that a set of servers handling requests, connected in a heterogeneous network, can be efficiently managed by a distributed algorithm. Additionally, even if the network is organizationally distributed, with individual organizations optimizing performance of their requests, the network remains efficient.
multiobjective scheduling
 Joseph Emeras, Vinicius Pinheiro, Krzysztof Rzadca, and Denis Trystram.
Ostrich: Fair scheduling for multiple submissions.
In PPAM 2013, International Conference on Parallel
Processing and Applied Mathematics, LNCS. Springer, 2013.
[ bib 
.pdf ]
Campaign Scheduling is characterized by multiple job submissions issued from multiple users over time. This model perfectly suits today's systems since most available parallel environments have multiple users sharing a common infrastructure. When scheduling individually the jobs submitted by various users, one crucial issue is to ensure fairness. This work presents a new fair scheduling algorithm called OStrich whose principle is to maintain a virtual timesharing schedule in which the same amount of processors is assigned to each user. The completion times in the virtual schedule determine the execution order on the physical processors. Then, the campaigns are interleaved in a fair way by OStrich. For independent sequential jobs, we show that OStrich guarantees the stretch of a campaign to be proportional to campaign's size and the total number of users. The stretch is used for measuring by what factor a workload is slowed down relative to the time it takes on an unloaded system. The theoretical performance of our solution is assessed by simulating OStrich compared to the classical FCFS algorithm, issued from synthetic workload traces generated by two different user profiles. This is done to demonstrate how OStrich benefits both types of users, in contrast to FCFS.

PierreFrancois Dutot, Fanny Pascual, Krzysztof Rzadca, and Denis Trystram.
Approximation algorithms for the multiorganization scheduling
problem.
IEEE Transactions on Parallel and Distributed Systems, 22:18881895, 2011.
[ bib 
DOI 
.pdf ]
The distributed nature of new computing platforms results in the problem of scheduling parallel jobs produced by several independent organizations that have each their own rules. They have no direct control over the whole system, thus it is necessary to revisit classical scheduling with locality constraints. In this article, we consider distributed computing systems in which each organization has its own resources. Each organization aims at minimizing the execution times of its own jobs. We introduce a global centralized mechanism for designing a collaborative solution that improves the global performance of the system while respecting organizations' selfish objectives. The proposed algorithm is proved to have an approximation ratio equal to 3 over the global optimal makespan and this bound is shown to be asymptotically tight (when the number of organizations is large). Several variants of this problem are also studied. Then, we derive another algorithm that improves in practice these solutions by further balancing the schedules. Finally, we provide some experiments based on simulations that demonstrate a very good efficiency of this last algorithm on typical instances.
 P.F Dutot, K. Rzadca, E. Saule, and D. Trystram. Multiobjective scheduling. In Y. Robert and F. Vivien, editors, Introduction to Scheduling, Computational Science. Chapman & Hall/CRC, 2009. [ bib  http ]
 F. Pascual, K. Rzadca, and D. Trystram.
Cooperation in multiorganization scheduling.
Concurrency&Computation: Practice and Experience, 21:905921,
2009.
[ bib 
DOI 
.pdf ]
The distributed nature of the grid results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. We consider systems in which each organization owns a cluster of processors. Each organization wants its tasks to be completed as soon as possible. In this paper, we model an offline system consisting of N identical clusters of m processors. We show that it is always possible to produce a collaborative solution that respects participants' selfish goals, at the same time improving the global performance of the system. We propose an algorithm (called MOLBA) with a guaranteed worstcase performance ratio on the global makespan, equal to 4. Next, we show that a better bound (equal to 3) can be obtained in a specific case when the last completed job requires at most m2 processors. Then, we derive another algorithm (called ILBA) that in practice improves the proposed, guaranteed solution by further balancing the schedules. Finally, by an extensive evaluation by simulation, we show that the algorithms are efficient on typical instances.
 K. Rzadca and D. Trystram.
Promoting cooperation in selfish computational grids.
European Journal of Operational Research, 199:647657, 2009.
[ bib 
DOI 
.pdf ]
In distributed computing the recent paradigm shift from centrallyowned clusters to organizationally distributed computational grids introduces a number of new challenges in resource management and scheduling. In this work, we study the problem of Selfish Load Balancing which extends the wellknown Load Balancing (LB) problem to scenarios in which each processor is concerned only with the performance of its local jobs. We propose a simple mathematical model for such systems and a novel function for computing the cost of the execution of foreign jobs. Then, we use the gametheoretic framework to analyze the model in order to compute the expected result of LB performed in a grid formed by two clusters. We show that, firstly, LB is a sociallyoptimal strategy, and secondly, for similarly loaded clusters, it is sufficient to collaborate during longer time periods in order to make LB the dominant strategy for each cluster. However, we show that if we allow clusters to make decisions depending on their current queue length, LB will never be performed. Then, we propose a LB algorithm which balances the load more equitably, even in the presence of overloaded clusters. Our algorithms do not use any external forms of compensation (such as money). The load is balanced only by considering the parameters of execution of jobs. This analysis is assessed experimentally by simulation, involving scenarios with multiple clusters and heterogeneous load.