A Truthful Load Balancing Mechanism with Verification
Abstract
In this paper we investigate the problem of designing load balancing protocols in distributed systems involving self-interested participants. These participants have their own requirements and objectives and no a-priori motivation for cooperation. Their selfish behavior may lead to poor performance and inefficiency. To address this problem we design a load balancing mechanism with verification that provides incentives to participants to report their true parameters and follow the given algorithm. We prove that our load balancing mechanism is truthful (i.e., agents will be better off by reporting their true parameters) and satisfies the voluntary participation condition (i.e., truthful agents never incur a loss). We present a simulation study to show the performance of our load balancing mechanism.
References
- Journal of Parallel and Distributed Computing 61(9), 1367 (2001), DOI: 10.1006/jpdc.2001.1754. Crossref, ISI, Google Scholar
A. Archer and E. Tardos , Truthful Mechanism for One-Parameter Agents, Proc. of the 42nd IEEE Symp. on Foundations of Computer Science (2001) pp. 482–491. Google ScholarA. Archer and E. Tardos , Frugal Path Mechanisms, Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (2002) pp. 991–999. Google Scholar- Public Choice 15, 17 (1971). Google Scholar
J. Feigenbaum , A BGP-based Mechanism for Lowest-Cost Routing, Proc. of the 21st ACM Symposium on Principles of Distributed Computing (2002) pp. 173–182. Google Scholar- Journal of Computer and System Sciences 63(1), 21 (2001), DOI: 10.1006/jcss.2001.1754. Crossref, ISI, Google Scholar
J. Feigenbaum and S. Shenker , Distributed Algorithmic Mechanism Design: Recent Results and Future Directions, Proc. of the 6th ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (2002) pp. 1–13. Google Scholar- IEEE Transactions on Systems, Man and Cybernetics 23(3), 902 (1993), DOI: 10.1109/21.256564. Crossref, ISI, Google Scholar
D. Grosu , A. T. Chronopoulos and M. Y. Leung , Load Balancing in Distributed Systems: An Approach Using Cooperative Games, Proc. of the 16th IEEE International Parallel and Distributed Processing Symposium (2002) pp. 501–510. Google Scholar- IEEE Transactions on Systems, Man and Cybernetics - Part B: Cybernetics 34(1), 77 (2004), DOI: 10.1109/TSMCB.2002.805812. Crossref, ISI, Google Scholar
- Econometrica 41(4), 617 (1973), DOI: 10.2307/1914085. Crossref, ISI, Google Scholar
J. Hershberger and S. Suri , Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proc. of the 42nd IEEE Symp. on Foundations of Computer Science (2001) pp. 252–259. Google Scholar-
H. Kameda , Optimal Load Balancing in Distributed Computer Systems ( Springer Verlag , London , 1997 ) . Crossref, Google Scholar R. Karp , Optimization Problems in Congestion Control, Proc. of the 41st IEEE Symp. on Foundations of Computer Science (2000) pp. 66–74. Google Scholar-
D. G. Luenberger , Linear and Nonlinear Programming ( Addison-Wesley , Reading, Mass. , 1984 ) . Google Scholar -
C. Ng , D. Parkes and M. Seltzer , Strategyproof computing: Systems infrastructures for self-interested parties , Proc. of the 1st Workshop on Economics of Peer-to-Peer Systems ( 2003 ) . Google Scholar N. Nisan , Globally Distributed Computation over Internet - The POPCORN Project, Proc. of the 18th IEEE International Conference on Distributed Computing Systems (1998) pp. 592–601. Google ScholarN. Nisan and A. Ronen , Algorithmic Mechanism Design, Proc. of the 31st Annual ACM Symp. on Theory of Computing (1999) pp. 129–140. Google Scholar- Games and Economic Behavior 35(1-2), 166 (2001), DOI: 10.1006/game.1999.0790. Crossref, ISI, Google Scholar
-
M. Osborne and A. Rubinstein , A Course in Game Theory ( MIT Press , Cambridge, Mass. , 1994 ) . Google Scholar A. Ronen , Algorithms for Rational Agents, Proc. of the 27th Conf. on Current Trends in Theory and Practice of Informatics,LNCS 1963 (Springer Verlag, 2000) pp. 56–70. Google ScholarT. Roughgarden , Stackelberg Scheduling Strategies, Proc. of the 33rd Annual ACM Symp. on Theory of Computing (2001) pp. 104–113. Google ScholarX. Tang and S. T. Chanson , Optimizing static Job Scheduling in a Network of Heterogeneous Computers, Proc. of the Intl. Conf. on Parallel Processing pp. 373–382. Google Scholar- Journal of Finance 16(1), 8 (1961), DOI: 10.2307/2977633. Crossref, ISI, Google Scholar
W. E. Walsh , Some Economics of Market-based Distributed Scheduling, Proc. of the 18th IEEE International Conference on Distributed Computing Systems (1998) pp. 612–621. Google Scholar-
R. Wolski , G-commerce: Market Formulations Controlling Resource Allocation on the Computational Grid , Proc. of the 15th IEEE International Parallel and Distributed Processing Symposium ( 2001 ) . Google Scholar


