The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Tight Analyses of Two Local Load Balancing Algorithms
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, Andr,
Pages. 29-64
Abstract
Contents 1. Introduction 1.1. Our results 1.2. Previous and related work 1.3. Outline 2.
Preliminaries 3. Analysis for static synchronous networks 3.1. The
single-port model 3.2. The multiport model 3.3. Results in terms
of node expansion 4. Local load balancing can be expensive 4.1. It
may be expensive to locally balance $G$ 4.2. The single-port
algorithm may diverge from an almost locally balanced state 4.3.
Convergence to a locally balanced state 5. Extension to dynamic
and asynchronous networks 6. Tight bounds on off-line load
balancing 7. Appendix A. Some technical inequalities 8. Appendix
B. Proof of Lemma 5.2
Key words load balancing, distributed network algorithms
Mathmatical Subject Classification 68Q22