Algorithmic Mechanism Design for Load Balancing in Distributed Systems
- 30 January 2004
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
- Vol. 34 (1) , 77-84
- https://doi.org/10.1109/tsmcb.2002.805812
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Globally distributed computation over the Internet-the POPCORN projectPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Optimization problems in congestion controlPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Distributed algorithmic mechanism designPublished by Association for Computing Machinery (ACM) ,2002
- A BGP-based mechanism for lowest-cost routingPublished by Association for Computing Machinery (ACM) ,2002
- Sharing the Cost of Multicast TransmissionsJournal of Computer and System Sciences, 2001
- Algorithmic Mechanism DesignGames and Economic Behavior, 2001
- Vickrey prices and shortest paths: what is an edge worth?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Computationally feasible VCG mechanismsPublished by Association for Computing Machinery (ACM) ,2000
- Optimal Load Balancing in Distributed Computer SystemsPublished by Springer Nature ,1997
- Multipart pricing of public goodsPublic Choice, 1971