Stand: 25. Juni 1998

»Load Balancing« Vorlesung im SS 98

Dozenten:

Artur Czumaj Raum:   F1.316 Tel.:   (05251) 60 64 91 Fax:   (05251) 60 64 82 EMail:   artur@uni-paderborn.de

Rolf Wanka Raum:   F1.125 Tel.:   (05251) 60 64 34 Fax:   (05251) 60 64 82 EMail:   wanka@uni-paderborn.de

Zeiten/Orte

Donnerstag		1130 - 1300		F2.211		(entfällt am 21.5., 4.6. und 11.6.)
Freitag		1330 - 1500		F1.225		(entfällt am 1.5, 15.5. und 5.6.)

Übungsblätter

• Blatt 1
• Blatt 2

Inhalt

1. Deterministische Load-Balancing-Verfahren
   1. Das Single-Token-Modell im statischen Fall
      1. Das Modell
      2. Eine einfache untere Schranke
      3. Eine allgemeine obere Schranke
         Exkurs: Flüsse auf Netzwerken
         1. Der Fluß-Graph
         2. Berechnung des minimalen Schnitts
      4. Adaptives online Load Balancing auf 2-dimensionalen Gittern
      5. log(k)-kompetitives Load Balancing auf 2-dimensionalen Gittern
      6. Übungen

   2. Das Multi-Token-Modell: Diffusion
      1. Das Modell
         Exkurs: Eigenwerte & Eigenvektoren
      2. Konvergenzgeschwindigkeit des Diffusions-Prozesses
      3. Die Abweichung zwischen Markov-Kette und realem Prozeß

2. Randomisierte Load-Balancing-Verfahren
   1. Ballwürfe in Kisten: Der klassische Prozeß
   2. Der »verbesserte« klassische Prozeß (von Azar u.a.)
   3. Adaptive Prozesse und Prozesse mit »reallocations«
   4. Untersuchung der Prozesse durch Differential-Gleichungen
   5. Parallele Prozesse

Literatur zu Abschnitt I.1

• Meyer auf der Heide, F.; Oesterdiekhoff, B.; Wanka, R.: Strongly Adaptive Token Distribution; Algorithmica 15 (1996) 413-427.
  PDF-File © 1996 Springer-Verlag

• Awerbuch, B.; Kutten, S.; Peleg, D.: Competitive Distributed Job Scheduling; in: Proc. 24th ACM Symposium on Theory of Computing (STOC) pp. 571-580, 1992.
  PS-File © 1992 ACM

• Deng, X.; Liu, H.-H.; Long, J.-S.; Xiao, B.: Competitive Analysis of Network Load Balancing; Journal of Parallel and Distributed Computing 40 (1997) 162-172.

• Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors; Journal of Parallel and Distributed Computing 7 (1989) 279-301.

• Rabani, Y.; Sinclair, A.; Wanka, R.: Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes; Mehr Informationen

• Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. Balanced allocations; in: Proc. 26th ACM Symposium on Theory of Computing (STOC), 593-602, 1994.
  PS-File © 1994 ACM

• A. Czumaj and V. Stemann. Randomized allocation processes; in: Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), 194-203, 1997.
  PS-File © 1997 IEEE

• M. Mitzenmacher. Load balancing and density dependent jump Markov processes; in: Proc. 37th IEEE Symposium on Foundations of Computer Science (FOCS), 213-222, 1996.
  PS-File © 1996 IEEE

• M. Mitzenmacher. Studying balanced allocations with differential equations; Technical Report SRC Technical Note 1997-024, System Research Center of Digital Equipment Corporation, Palo Alto, October 1997.
  PS-File © 1997 DEC

• M. D. Mitzenmacher. The Power of Two Choices in Randomized Load Balancing; PhD thesis, Computer Science Department, University of California at Berkeley, September 1996.
  PS-File © 1996

• M. Adler, S. Chakrabarti, M. Mitzenmacher, and L. Rasmussen. Parallel randomized load balancing; in: Proc. 27th ACM Symposium on Theory of Computing (STOC), 238-247, 1995.
  PS-File © 1995 ACM

• P. Berenbrink, F. Meyer auf der Heide, and K. Schröder. Allocating weighted jobs in parallel; in: Proc. 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), 302-310, 1997.
  ACM Press, New York, NY. PS-File © 1995 ACM

• V. Stemann. Parallel balanced allocations; in: Proc. 8th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), 261-269, 1996.
  PS-File © 1995 ACM