World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

A Truthful Load Balancing Mechanism with Verification

    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

    • E. Altmanet al., Journal of Parallel and Distributed Computing 61(9), 1367 (2001), DOI: 10.1006/jpdc.2001.1754. Crossref, ISIGoogle 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 Scholar
    • A. Archer and E. Tardos, Frugal Path Mechanisms, Proc. of the 13th Annual ACM-SIAM Symp. on Discrete Algorithms (2002) pp. 991–999. Google Scholar
    • E. Clarke, Public Choice 15, 17 (1971). Google Scholar
    • J. Feigenbaumet al., 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
    • J. Feigenbaum, C. Papadimitriou and S. Shenker, Journal of Computer and System Sciences 63(1), 21 (2001), DOI: 10.1006/jcss.2001.1754. Crossref, ISIGoogle 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
    • A. Glockner and J. Pasquale, IEEE Transactions on Systems, Man and Cybernetics 23(3), 902 (1993), DOI: 10.1109/21.256564. Crossref, ISIGoogle 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
    • D. Grosu and A. T. Chronopoulos, IEEE Transactions on Systems, Man and Cybernetics - Part B: Cybernetics 34(1), 77 (2004), DOI: 10.1109/TSMCB.2002.805812. Crossref, ISIGoogle Scholar
    • T. Groves, Econometrica 41(4), 617 (1973), DOI: 10.2307/1914085. Crossref, ISIGoogle 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 et al. , Optimal Load Balancing in Distributed Computer Systems ( Springer Verlag , London , 1997 ) . CrossrefGoogle Scholar
    • R. Karpet al., 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. Nisanet al., Globally Distributed Computation over Internet - The POPCORN Project, Proc. of the 18th IEEE International Conference on Distributed Computing Systems (1998) pp. 592–601. Google Scholar
    • N. Nisan and A. Ronen, Algorithmic Mechanism Design, Proc. of the 31st Annual ACM Symp. on Theory of Computing (1999) pp. 129–140. Google Scholar
    • N. Nisan and A. Ronen, Games and Economic Behavior 35(1-2), 166 (2001), DOI: 10.1006/game.1999.0790. Crossref, ISIGoogle 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 Scholar
    • T. Roughgarden, Stackelberg Scheduling Strategies, Proc. of the 33rd Annual ACM Symp. on Theory of Computing (2001) pp. 104–113. Google Scholar
    • X. 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
    • W. Vickrey, Journal of Finance 16(1), 8 (1961), DOI: 10.2307/2977633. Crossref, ISIGoogle Scholar
    • W. E. Walshet al., 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 et al. , 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