Textdokument
Randomisierte Protokolle für die Verteilung von Information
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2009
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Die in diesem Beitrag zusammengefasste Dissertation befaßt sich mit der Entwicklung und Analyse von zufälligen Algorithmen für das Verteilen von Information in Netzwerken. Zunächst wird das Problem der Verbreitung von Nachrichten (Rumor Spreading) betrachtet. Wir analysieren zunächst eine klassische, vollständig zufällige Variante (Randomized Rumor Spreading) und geben für verschiedene untersuchte Graphklassen verbesserte Laufzeitschranken an. Zudem untersuchen wir die Beziehung von Randomized Rumor Spreading und Irrfahrten. Wir geben zwei Parameter von Irrfahrten an, mit denen sich die Laufzeit von Randomized Rumor Spreading sowohl nach oben als auch nach unten abschätzen lässt. Neben der Analyse von diesen klassischen Algorithmen entwickeln wir auch eine neue Variante für das Verteilen von Nachrichten. Überraschenderweise können wir zeigen, daß diese neue Variante trotz reduzierten Zufalls dieselben oder sogar leicht bessere Ergebnisse als die klassische Variante erzielt. Schließlich beschäftigen wir uns mit der Balancierung von Lasteinheiten. Wir geben ein sehr einfaches Netzwerk an, das unter Zuhilfenahme von Zufall beliebige Eingangslasten bis auf einen kleinen additiven Faktor balanciert. Hierbei ist die benötigte Zeit nahezu optimal und gleichzeitig der additive Faktor unabhängig von der Gesamtlast und der initialen Balanciertheit.