Algorithmic mechanism design for load balancing in distributed systems

Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2004-02, Vol.34 (1), p.77-84
Main Authors: Grosu, D., Chronopoulos, A.T.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Cost accounting
Degradation
Distributed computing
Game theory
Grid computing
Large-scale systems
Load management
Protocols
Resource management
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mechanism design theory. Using this theory, we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness.
ISSN:1083-4419
2168-2267
1941-0492
2168-2275
DOI:10.1109/TSMCB.2002.805812