Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Prisoner's Dilemma in Heterogeneous Grids

SpeakerKrzysztof Rzadca

Co-authorDenis Trystram

The recent paradigm shift in distributed computation from centralized clusters to organizationally distributed grids introduces a number of new challenges in resource management and scheduling. As a grid is composed of resources owned by many independent organizations, their multiple goals must be fulfilled. Consequently, multi-criteria optimization and game theory must be used to study such systems.

In this work we propose a model in which each organization owns a specialized piece of equipment (a dedicated processor), yet also has jobs that must be computed on processors belonging to another organizations. We consider the problem of off-line ordering of sets of jobs (originating from different organizations) on each processor. Firstly, we show that only n job ordering strategies (out of n!) for each organization are not dominated. Then, in a system composed of two organizations, we show the ordering problem can be reduced to the well-known Prisoner's Dilemma game. Finally, we consider a heterogeneous case in which one organization has significantly more jobs to compute on the other processor. We propose a notion of a fair solution, which is Pareto-optimal and equitably dominates all other outcomes. We show that this solution is the equivalent of mutual cooperation in the Prisoner's Dilemma.