Load balancing is about distributing work load (jobs, tasks, processes, etc.) among a set of processing facilities (processors, workstations, servers, etc.), such that, usually, this load is more or less evenly distributed. In this work we introduce and investigate the performance of three randomised load balancing algorithms for dynamic settings, that is, we are interested mostly in the long term behaviour of the algorithms, and here especially in deriving an upper bound on the maximum load of any server at any point of time. We assume two fundamentally different load generation schemes. First, we analyse the algorithms given a stochastical scheme, i.e., the generation and consumption of load obeys some probabilistic distribution. Second, we introduce an adversarial scheme, where we assume that the generation and consumption of load is controlled by an adversary, who deliberately tries to produce a load distribution as uneven as possible. Two of our algorithms are for the stochastical generation scheme, and the third one is for the adversarial scheme. After rigorously analysing the performance of the algorithms, we present some simulation results that indicate that under certain conditions our algorithms very are well-behaved in practice, too. Since the algorithms are somewhat theoretical in nature, we also briefly discuss how to modify them and tune certain parameters in order to make them even more applicable for practical problems.     «

Load balancing is about distributing work load (jobs, tasks, processes, etc.) among a set of processing facilities (processors, workstations, servers, etc.), such that, usually, this load is more or less evenly distributed. In this work we introduce and investigate the performance of three randomised load balancing algorithms for dynamic settings, that is, we are interested mostly in the long term behaviour of the algorithms, and here especially in deriving an upper bound on the maximum load of...     »

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.     «

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....     »