Abstract in English

Bei Lastbalancierung geht es um die Verteilung von Last (Jobs, Tasks, Prozesse, etc.) auf einer Menge von Maschinen (Prozessoren, Arbeitsstationen, Server, etc.), so dass, gewöhnlicherweise, diese Last mehr oder weniger gleichmäßig verteilt ist. In dieser Arbeit führen wir drei randomisierte Lastbalancierungsalgorithmen für dynamische Systeme ein und untersuchen deren Performance. Wir sind überwiegend interessiert am Langzeitverhalten der Algorithmen, und hier speziell an oberen Schranken bzgl. der maximalen Last eines jeden Servers zu einem beliebigen Zeitpunkt. Wir betrachten zwei fundamental unterschiedliche Lastgenerierungsschemata. Zuerst untersuchen wir die Algorithmen unter einem stochastischen Schema, d.h., Generierung und Abarbeitung der Last gehorcht einer gewissen Wahrscheinlichkeitsverteilung. Dann führen wir ein Gegenspielermodell ein, in dem Generierung und Abarbeitung von einem Gegenspieler kontrolliert ist, der bewußt versucht, eine möglichst unebene Lastverteilung zu produzieren. Zwei unserer Algorithmen sind für das stochastische Modell, und der dritte für das Gegenspielermodell. Nachdem die Performance der Algorithmen gründlich analysiert wurde, präsentieren wir einige Simulationsresultate, die indizieren, dass unsere Algorithmen unter bestimmten Umständen in der Praxis sehr gute Ergebnisse liefern. Da die Algorithmen recht theoretischer Natur sind, gehen wir auch kurz darauf ein, wie man sie modifizieren kann, um sie sogar noch praxisrelevanter zu machen.