CaltechAUTHORS
  A Caltech Library Service

FCD: Fast-concurrent-distributed load balancing under switching costs and imperfect observations

Huang, Furong and Anandkumar, Animashree (2013) FCD: Fast-concurrent-distributed load balancing under switching costs and imperfect observations. In: 2013 Proceedings IEEE INFOCOM. IEEE , Piscataway, NJ, pp. 1896-1904. ISBN 978-1-4673-5944-3. https://resolver.caltech.edu/CaltechAUTHORS:20170925-100358224

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170925-100358224

Abstract

The problem of distributed load balancing among m agents operating in an n-server slotted system is considered. A randomized local search mechanism, FCD (fast, concurrent and distributed) algorithm, is implemented concurrently by each agent associated with a user. It involves switching to a different server with a certain exploration probability and then backtracking with a probability proportional to the ratio of the measured loads in the two servers (in consecutive time slots). The exploration and backtracking operations are executed concurrently by users in local alternating time slots. To ensure that users do not switch to other servers asymptotically, each user chooses the exploration probability to be decaying polynomially with time for decaying rate β ∈ [0.5, 1]. The backtracking decision is then based on an estimate of the server load which is computed based on local information. Thus, FCD algorithm does not require synchronization or coordination with other users. The main contribution of this work, besides the FCD algorithm, is the analysis of the convergence time for the system to be approximately balanced, i.e. to reach an c-Nash equilibrium. We show that the system reaches an c-Nash equilibrium in expected time O (max {n log n/ϵ + n^(1/β), (n^3/m^3 log n^2/ϵ)1/β}) when m > n^2. This implies that the convergence rate is robust with large scale system(large user population), and is not affected by imperfect measurements of the server load. We also extend our analysis to open systems where users arrive and depart from a system with an initial load of m users. We allow for general time-dependent arrival processes (including heavy-tailed processes) and consider a uniform and a load-oblivious routing of the arrivals to the servers. A wide class of departure processes including load-dependent departures from the servers is also allowed. Our analysis demonstrates that it is possible to design fast, concurrent and distributed load balancing mechanisms in large multi-agent systems via randomized local search.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/INFCOM.2013.6566989DOIArticle
http://ieeexplore.ieee.org/document/6566989PublisherArticle
Additional Information:© 2013 IEEE.
Subject Keywords:Servers, Convergence, Load management, Switches, Open systems, Games, Nash equilibrium
DOI:10.1109/INFCOM.2013.6566989
Record Number:CaltechAUTHORS:20170925-100358224
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170925-100358224
Official Citation:F. Huang and A. Anandkumar, "FCD: Fast-concurrent-distributed load balancing under switching costs and imperfect observations," 2013 Proceedings IEEE INFOCOM, Turin, 2013, pp. 1896-1904. doi: 10.1109/INFCOM.2013.6566989 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6566989&isnumber=6566708
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81803
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:25 Sep 2017 17:09
Last Modified:15 Nov 2021 19:46

Repository Staff Only: item control page