A Statistical Mechanical Load Balancer for the Web
arXiv:cond-mat/0410136 · doi:10.1103/PhysRevE.71.046133
Abstract
The maximum entropy principle from statistical mechanics states that a closed system attains an equilibrium distribution that maximizes its entropy. We first show that for graphs with fixed number of edges one can define a stochastic edge dynamic that can serve as an effective thermalization scheme, and hence, the underlying graphs are expected to attain their maximum-entropy states, which turn out to be Erdos-Renyi (ER) random graphs. We next show that (i) a rate-equation based analysis of node degree distribution does indeed confirm the maximum-entropy principle, and (ii) the edge dynamic can be effectively implemented using short random walks on the underlying graphs, leading to a local algorithm for the generation of ER random graphs. The resulting statistical mechanical system can be adapted to provide a distributed and local (i.e., without any centralized monitoring) mechanism for load balancing, which can have a significant impact in increasing the efficiency and utilization of both the Internet (e.g., efficient web mirroring), and large-scale computing infrastructure (e.g., cluster and grid computing).
11 Pages, 5 Postscript figures; added references, expanded on protocol discussion
References in corpus (13)
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Network robustness and fragility: Percolation on random graphs
- Renormalization group analysis of the small-world network model
- Scaling and percolation in the small-world network model
- Bose-Einstein condensation in complex networks
- Scaling laws for the movement of people between locations in a large city
- Exact solution of site and bond percolation on small-world networks
- Statistical ensemble of scale-free random graphs
- Correlated random networks
- Scale-Free and Stable Structures in Complex {\em Ad hoc} networks
- Uncorrelated Random Networks
- Principles of statistical mechanics of random networks