Date Added: Jan 2010
This paper investigates scheduling loosely coupled task-bundles in highly heterogeneous distributed systems. Two allocation quality metrics are used in pay-per-service distributed applications: efficiency in terms of social welfare, and fairness in terms of envy-freeness. The first contribution of this work is that the authors build a unified hyper-graph scheduling model under which efficiency and fairness are compatible with each other. Second, in the scenario of budget-unawareness, they formulate a strategic algorithm design for distributed negotiations among autonomous self-interested computing peers and prove its convergence to complete local efficiency and envy-freeness.