Coordination Mechanisms for Selfish Multi-Organization Scheduling

Johanne Cohen; Daniel Cordeiro; Denis Trystram; Frédéric Wagner

doi:10.1109/HiPC.2011.6152720

Coordination Mechanisms for Selfish Multi-Organization Scheduling

Johanne Cohen ¹ Daniel Cordeiro ^{2, 3} Denis Trystram ² Frédéric Wagner ²

1 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation

2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation

Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble

3 LIG - Laboratoire d'Informatique de Grenoble

Abstract : We conduct a game theoretic analysis on the problem of scheduling jobs on computing platforms composed of several independent and selfish organizations, known as the Multi-Organization Scheduling Problem (MOSP). Each organization shares resources and jobs with others, expecting to decrease the makespan of its own jobs. We modeled MOSP as a non-cooperative game where each agent is responsible for assigning all jobs belonging to a particular organization to the available processors. The local scheduling of these jobs is defined by coordination mechanisms that first prioritize local jobs and then schedule the jobs from others according to some given priority. When different priorities are given individually to the jobs ―- like in classical scheduling algorithms such as LPT or SPT ―- then no pure ε-approximate equilibrium is possible for values of ε less than 2. We also prove that even deciding whether a given instance admits or not a pure Nash equilibrium is co-NP hard. When these priorities are given to entire organizations, we show the existence of an algorithm that always computes a pure ρ-approximate equilibrium using any ρ-approximation list scheduling algorithm. Finally, we prove that the price of anarchy of the MOSP game using this mechanism is asymptotically bounded by 2.

Type de document :

Communication dans un congrès

Proceedings of the 18th annual IEEE International Conference on High Performance Computing (HiPC), 2011, Bangalore, India. IEEE Computer Society, 2011, <10.1109/HiPC.2011.6152720>

Domaine :

Informatique [cs] / Calcul parallèle, distribué et partagé [cs.DC]

Liste complète des métadonnées

https://hal.inria.fr/hal-00796864
Contributeur : Grégory Mounié <>
Soumis le : mardi 5 mars 2013 - 11:06:21
Dernière modification le : jeudi 9 février 2017 - 15:46:57

Coordination Mechanisms for Selfish Multi-Organization Scheduling

Identifiants

Collections

Citation

Exporter

Métriques

159

Coordination Mechanisms for Selfish Multi-Organization Scheduling

Identifiants

Collections

Citation

Exporter

Partager

Métriques

159