English

In this thesis we investigate the impact of randomization for information dissemination on networks. We begin by studying the runtime of the so-called push algorithm for disseminating a rumor initially known by a single node to all other nodes of a network modelled by an undirected, connected graph. We upper bound the runtime of this algorithm on general and more specific networks. We also consider the relationship of the push algorithm to random walks. More precisely, we relate the runtime of the push algorithm to the mixing time (first step the distribution of the random walk is close to equilibrium) and the cover time (first step the random walk has visited all vertices). In particular, we provide a fairly tight characterization of graphs where the cover time and runtime of the push algorithm are capturing each other (neglecting small factors). We also propose and analyze a new variant of the push algorithm called quasirandom rumor spreading. Though this variant requires much less random bits, we prove that the performance is at least as good (or even better) as the classical push algorithm on two important networks. Finally, we consider smoothing networks, which are designed for load balancing of indivisible tokens in a distributed environment. Assuming a random initialization, we present a very simple network that balances the load up to an additive constant, regardless of the imbalance of the input. Our results do not only reveal the power of randomization, but also demonstrate that small changes in the protocol may sometimes lead to surprisingly vast improvements.

Deutsch

In dieser Arbeit untersuchen wir den Einfluss von Zufall für das Verbreiten von Information auf Netzwerken. Wir betrachten zunächst die Laufzeit des sogenannten Push-Verfahrens, das eine Nachricht eines Knotens an alle anderen Knoten eines Netzwerks verteilt. Hierbei wird das Netzwerk durch einen ungerichteten, zusammenhängenden Graphen modelliert. Wir leiten obere Schranken auf die Laufzeit des Push-Verfahrens für allgemeine und spezielle Netzwerke her. Auch die Beziehung des Push-Verfahrens zu Zufallsirrfahrten wird untersucht. Wir beweisen Laufzeitschranken, die von der Mischzeit (Zeit bis das die Zufallsirrfahrt nahezu stationär verteilt ist) und der Überdeckungszeit (Zeit bis das die Zufallsirrfahrt alle Knoten besucht hat) abhängen. Insbesondere geben wir eine recht genaue Charakterisierung der Graphklasse an, für die die Überdeckungszeit die Laufzeit des Push-Verfahrens bis auf kleine Faktoren bestimmt. Wir entwickeln und analysieren auch ein quasi zufälliges Verfahren für das Verbreiten einer Nachricht. Obwohl dieses Verfahren viel weniger Zufallsbits benötigt, zeigen wir, dass auf zwei wichtigen Netzwerken die Laufzeit mindestens so gut wie (oder sogar besser als) das klassische Push-Verfahren ist. Schließlich betrachten wir Smoothing-Netzwerke, die für die Balancierung unteilbarer Last in einem verteilten System geeignet sind. Unter der Annahme einer zufälligen Initialisierung geben wir ein sehr einfaches Netzwerk an, was die Last bis auf eine additive Konstante balanciert, unabhängig von der Unbalanciertheit der Eingabe. Unsere Resultate demonstrieren nicht nur das Potential von zufälligen Algorithmen, sondern zeigen auch, dass kleine Änderungen am Protokoll zu überraschend deutlichen Verbesserungen führen können.