Lehrstuhl für Effiziente Algorithmendes Instituts für Informatikder Technischen Universität MünchenRandomised DynamicLoad BalancingTom FriedetzkyVollständigerAbdruckdervonderFakultätfürInformatikderTechnischenUniversität München zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr. Dr. h.c. W. BrauerPrüfer der Dissertation:1. Univ.-Prof. Dr. E.W. Mayr2. Univ.-Prof. Dr. F. Meyer auf der Heide,Universität Gesamthochschule PaderbornDie Dissertation wurde am 28.06.2000 bei der Technischen UniversitätMünchen eingereicht und durch die Fakultät für Informatik am 16.08.2002angenommen.AcknowledgementsThere are many people I would like to express my thanks to. My first big“thank you” goes to my mother. For everything. The second one goes tomy brother, who never ceased to remind me that it indeed is a bit oddthat serious people spend some considerable time and effort in analysingthe process of randomlythrowing balls into bins. Can’t say I blamehim...Further thanks go to two persons I have had the luck to meet during mytime at universities. In chronological order: I am deeply indebted to theadvisor of my master’s thesis, Prof. Dr. Friedhelm Meyer auf der Heide.Blame him for waking the love for theoretical computer science in me. I ofcourse also owe thanks to the advisor of this PhD thesis, Prof. Dr. ErnstW.