Forschungsbericht 2008 - Max-Planck-Institut für Informatik

Zufällige Telefonketten

Autoren
Doerr, Benjamin
Abteilungen

Algorithmen und Komplexität (Prof. Dr. Dr.-Ing. E.h. Kurt Mehlhorn)
MPI für Informatik, Saarbrücken

Zusammenfassung
Eine Telefonkette ist ein Verfahren, das eine Nachricht an alle Mitglieder einer Gruppe verbreitet. Ähnliche Aufgaben werden auch in der Informatik untersucht. Erstaunlich gut sind dabei Telefonketten, die zufällige Entscheidungen treffen. Wie viel Zufall dabei optimal ist, ist ein Gegenstand der aktuellen Forschung.

Was haben die James-Krüss-Schule Helgoland und die Ministranten-Schar aus Bazenheid gemeinsam? Sie nutzen eine Telefonkette, um eilige Nachrichten an alle Mitglieder der Gruppe zu kommunizieren. Im einfachsten Fall basiert die Telefonkette auf einer geordneten Liste der Gruppenmitglieder. Die zu verbreitende Neuigkeit wird zunächst dem ersten auf dieser Liste mitgeteilt. Der ruft nun den zweiten an, der den dritten, und so weiter. Komplexere Telefonketten erreichen eine schnellere Informationsverbreitung dadurch, dass einige Teilnehmer mehr als nur einen weiteren anrufen. Ein solches Schema ist in Abbildung 1 dargestellt.

In der Informatik treten ähnliche Aufgabenstellungen auf, etwa wenn Informationen in Rechnernetzen verbreitet werden müssen. Im vorliegenden Artikel sollen diese Probleme zunächst skizziert werden. Dann stellen wir einen überraschend einfachen Lösungsansatz vor, der ausschließlich aus zufälligen Anrufen besteht. Darauf aufbauend wollen wir ein ganz aktuelles Thema aus der Forschung beschreiben, nämlich wie man mit der richtigen Dosis Zufall derartige Verfahren signifikant verbessern kann.

Telefonkettenprobleme in der Informatik

Das Problem, eine Information zügig an alle Mitglieder einer Gruppe zu verbreiten, tritt in der Informatik bei der Verwendung replizierter Datenbanken auf. Ein Unternehmen mit Filialen an mehreren Standorten könnte seine Kundendaten in jeder Filiale lokal speichern. Dies hat den Vorteil, dass in jeder Filiale schnell und unkompliziert auf diese Daten zugegriffen werden kann, und dass die Daten auch bei kurzzeitiger Nichterreichbarkeit der zentralen Datenbank zur Verfügung stehen. Bei Verwendung solcher replizierter Datenbanken müssen natürlich Änderungen, die sich im Datenbestand einer Filiale ergeben, zügig an alle anderen kommuniziert werden.

In zwei zentralen Aspekten unterscheidet sich dieses Telefonkettenproblem der Informatik von dem der Alltagswelt. Erstens können solche Datenbanksysteme sehr groß sein. Bei einem Netz von einigen tausend Knoten würde die Informationsausbreitung viel zu lange dauern, wenn die Knoten in einer festen Reihenfolge nacheinander die Nachricht weitergeben.

Ein zweiter Punkt ist die Robustheit des Verfahrens. Unter Robustheit versteht man, dass ein Verfahren auch dann noch gut funktionieren soll, wenn einzelne Teilschritte nicht ganz so abgelaufen sind, wie man es erhofft hat. Bei einer Telefonkette ist dies hauptsächlich das Problem, dass ein Teilnehmer nicht erreichbar ist, oder dass er zwar erreichbar ist, aber dann aus irgendwelchen Gründen die Nachricht nicht weitergibt. Die klassische sequentielle Telefonkette ist augenscheinlich nicht sehr robust. Wenn ein Teilnehmer die Nachricht nicht weitergibt, bleiben alle nachfolgenden Teilnehmer uninformiert. Es bleibt also festzustellen, dass die klassische Telefonkette, auch mit den üblicherweise genutzten kleinen Verbesserungen, für die Verwendung in der Informatik eher ungeeignet ist. Sie ist viel zu langsam und nicht robust.

Zufällige Telefonketten

Für Telefonkettenprobleme in der Informatik gibt es eine überraschend einfache Lösung, die gleichzeitig sehr effizient und robust ist. Bei der zufälligen Telefonkette ruft jeder, der die Nachricht kennt, zufällig gewählte andere Teilnehmer an. Zur Vereinfachung der Darstellung sei angenommen, dass alle Anrufe gleich lange benötigen. Dies führt dazu, dass der Informationsaustausch in Runden abläuft. In jeder Runde ruft jeder informierte Teilnehmer bei einem zufällig gewählten anderen Teilnehmer an. Dieser ist dann spätestens ab diesem Zeitpunkt ebenfalls informiert.

Für eine menschliche Telefonkette ist dieses Verfahren weniger geeignet, unter anderem, weil es unfair ist. Ein Teilnehmer, der sehr früh informiert wird, muss viel mehr telefonieren als einer, der erst später informiert wird. Für den rechnergestützten Informationsaustausch ist dies weniger relevant. Hier stehen Effizienz und Robustheit im Vordergrund. In diesen beiden Punkten ist die zufällige Telefonkette unglaublich stark. Nehmen wir als Beispiel ein Datennetz mit 1024 Knoten. Dann benötigt die zufällige Telefonkette im Schnitt nur 18,09 Runden, bis alle Knoten informiert wurden. Ähnlich gut sieht es mit der Robustheit aus. Selbst wenn wir annehmen, dass jeder zehnte Teilnehmer nie erreichbar ist, genügen im Schnitt nur 19,49 Runden, um die übrigen zu informieren. Dabei spielt es keine Rolle, welche 10% der Teilnehmer ausfallen.

Nachteile der Zufälligkeit

Wir haben gesehen, dass die zufällige Telefonkette ein sehr effizientes und robustes Protokoll zum Informationsaustausch in Computernetzen ist. Der Grund liegt darin, dass wir alle Entscheidungen zufällig und unabhängig voneinander treffen. Dies führt jedoch auch zu unschönen Effekten. So kann es beispielsweise passieren, dass ein Knoten mehrfach hintereinander beim selben anderen Knoten anruft. Das ist natürlich unsinnig – schon nach dem ersten Anruf ist der andere Knoten informiert und alle weiteren Anrufe sind vergeudet.

Neben diesem offensichtlichen Problem gibt es auch technische Gründe, die gegen einen übertriebenen Nutzen von Zufall sprechen. Zum einen ist es für einen Computer gar nicht so einfach, eine gute Zufallszahl zu erzeugen. Zum anderen erschweren die zufälligen Entscheidungen im Programmablauf die Fehlersuche und die Kontrolle, ob das Programm korrekt arbeitet. Um die Berechnungsfolge nachvollziehen zu können, muss der Programmierer alle Zufallsentscheidungen dokumentieren.

Quasizufällige Telefonketten

Um diesen Effekten entgegenzuwirken, haben Tobias Friedrich, Thomas Sauerwald und Benjamin Doerr [1] folgende Variante der zufälligen Telefonkette vorgeschlagen, die quasizufällige Telefonkette. Wir nehmen an, dass jeder Teilnehmer eine Liste aller anderen Teilnehmer besitzt. Es ist nicht notwendig, dass diese Listen eine spezielle Ordnung haben. Insbesondere kann jeder Teilnehmer eine unterschiedliche Liste besitzen. Die Annahme, dass solche Listen vorliegen, ist relativ natürlich. Bei einer Telefonkette zwischen Menschen könnte dies beispielsweise eine Adressenliste der betreffenden Gruppe sein. Beim Datenabgleichproblem zwischen Computern muss jeder Rechner ebenfalls über Informationen verfügen, mit welchen anderen Rechnern er wie kommunizieren kann. Diese Information wird typischerweise ebenfalls in einer geordneten Liste gespeichert.

Bei der quasizufälligen Telefonkette ist nur der erste Anruf eines jeden Teilnehmers zufällig. Alle weiteren Anrufe folgen der Liste. In anderen Worten: Sowie ein Teilnehmer die Nachricht erhält, bestimmt er einen zufälligen Startpunkt auf seiner Liste. Dann ruft er in jeder Runde bei einem anderen an, wobei er an diesem Startpunkt beginnt und sich dann auf der Liste nach unten weiterarbeitet. Falls er das Ende der Liste erreicht, so macht er am Anfang weiter.

Ganz offenbar erreicht das listengesteuerte Vorgehen, dass kein Teilnehmer einen anderen mehrfach anruft, es sei denn, er hat schon alle anderen einmal angerufen. Ebenso ist es leicht zu sehen, dass dieses Protokoll viel weniger Zufallsentscheidungen nutzt. Während in einer zufälligen Telefonkette jede Nachricht an ein zufälliges Ziel geschickt wird, sendet hier jeder Teilnehmer nur eine einzige zufällige Nachricht aus. Alle übrige Kommunikation ist durch die Listen festgelegt. Die spannende Frage ist, ob dieses quasizufällige Protokoll ebenso schnell und robust ist wie das vollständig zufällige.

Effizienz und Robustheit der quasirandomisierten Telefonkette

Für einen ersten einfachen Vergleich der beiden Verfahren haben wir das quasirandomisierte Verfahren implementiert und experimentell evaluiert. Wie oben wollten wir wissen, wie lange 1024 Teilnehmer benötigen, um eine Nachricht an alle weiterzuleiten. Wir haben dabei die Teilnehmer durchnumeriert. Die Liste jedes Teilnehmers bestand aus den übrigen Teilnehmern in aufsteigender Reihenfolge. In diesem Aufbau haben wir gemessen, dass nach durchschnittlich 17,63 Runden alle Teilnehmer die Nachricht erhalten haben. Das ist 2,5% schneller als bei der randomisierten Telefonkette. Selbst wenn wir annehmen, dass ein Zehntel der Teilnehmer nicht erreichbar ist, so sind nach durchschnittlich 19,16 Runden alle anderen informiert.

Es zeigt sich also, dass mit der kleinen Modifikation hin zum quasirandomisierten Modell ein kleiner, aber messbarer Vorteil erzielt wurde. Dennoch hat das Weniger an Zufall nicht zu Nachteilen bei der Robustheit geführt. Bisher sind wir davon ausgegangen, dass jeder Teilnehmer mit jedem anderen kommunizieren kann. Rechnernetzwerke haben typischerweise eine andere Struktur. Aus Kostengründen organisiert man solche Netze normalerweise so, dass jeder Knoten des Netzes nur mit wenigen anderen (seinen „Nachbarn“) direkt kommunizieren kann. Mit allen anderen muss indirekt, also über Zwischenstationen kommuniziert werden.

In der Informatik existieren unterschiedliche Modelle für solche Netze. Um Aussagen von einer gewissen Allgemeingültigkeit zu erzielen, kann man derartige Netze zufällig erzeugen. Ein klassisches Modell dafür stammt von den ungarischen Mathematikern Erdős und Rényi [2]. Für jedes Paar von Knoten wird hier mit einer festen Wahrscheinlichkeit p eine direkte Verbindung zwischen diesen Knoten gezogen. Wir wählten p = 10/1023. Damit besitzt jeder der 1024 Knoten im Schnitt 10 Nachbarn.

Vergleicht man die randomisierte Telefonkette mit der quasirandomisierten für dieses Netzwerkmodell, so zeigen sich sehr klare Unterschiede. Während das randomisierte Modell im Schnitt 27,31 Runden benötigt, schafft es das quasirandomisierte schon in 19,48 Runden. Das randomisierte Modell ist also gut 40% langsamer. Bei Netzwerken mit wenigen Verbindungen zwischen den Knoten ist das quasirandomisierte Verfahren also deutlich überlegener.

Leistungsanalysen in der Informatik: Experimente und Mathematik

Die skizzierten experimentellen Untersuchungen bezogen sich alle auf einen speziellen Typ von Listen, nämlich aufsteigend in der Knotennummer. Weiter oben hatten wir die Hoffnung gehegt, dass man Listen nutzen könnte, die schon implizit gegeben sind. Hier können wir also keine speziellen Annahmen an die Struktur der Listen machen. Vielmehr bräuchten wir Resultate, die für alle Arten von Listen gelten. Leider gibt es unheimlich viele Weisen, wie solche Listen aufgebaut sein könnten. Selbst wenn wir nur 1024 Knoten haben und jeder nur drei fest bestimmte Nachbarn hat, so gibt es noch 21024 strukturell verschiedene Möglichkeiten, Listen für alle Knoten zu bestimmen. Dies ist eine Zahl mit über 300 Stellen! Es ist also völlig ausgeschlossen, diese Möglichkeiten alle durchzuprobieren.

Wenn wir dennoch Erkenntnisse mit Gültigkeit für alle Listentypen erzielen wollen, müssen wir andere Methoden nutzen. Hier kommt uns eine der ältesten Wissenschaften zur Hilfe, die Mathematik. Mit mathematischen Methoden können wir Aussagen gewinnen über so große Anzahlen von Konstellationen, wie es kein Computer der Welt kann. Mit mathematischen Methoden ist es sogar möglich, Aussagen über unendlich viele Konstellationen zu gewinnen. Ein klassisches Beispiel hierfür ist die Aussage, dass es unendlich viele Primzahlen gibt. Für unser Problem werden Aussagen von Interesse sein, die garantieren, dass unsere Telefonketten für alle möglichen Zahlen von Teilnehmern und alle Arten von Listen gut funktionieren.

Ein solcher Beweis ist den Wissenschaftlern des MPI für Informatik nun gelungen. Sie konnten Folgendes zeigen. Für jeden noch so kleinen Fehlerparameter ε > 0 und für alle möglichen Anzahlen n der Teilnehmer (ab einer gewissen Größe) gelingt es dem quasirandomisierten Protokoll im Schnitt in weniger als (1,6932 + ε) log2(n) Runden, alle Teilnehmer zu informieren. Diese Garantie gilt unabhängig von der Art der verwendeten Listen. Mit diesem Ergebnis können wir guten Gewissens beliebige Listen verwenden, also auch solche, die schon aus anderen Gründen vorhanden sind. Ein kleiner Ausschnitt dieses Beweises ist in Abbildung 2 dargestellt.

Es mag überraschen, dass das gute Verhalten des quasirandomisierten Protokolls für alle Teilnehmerzahlen erst ab einer gewissen Größe bewiesen werden konnte. Intuitiv würde man ja eher annehmen, dass kleine Problemgrößen leichter zu analysieren wären. Dies ist aber in der Tat nicht der Fall. Der Grund liegt, unter anderem, im sogenannten Gesetz der großen Zahlen.

Die beschriebenen Arbeiten sind ein schönes Beispiel für das Zusammenspiel experimenteller und theoretischer Methoden in der Informatik. Die Theorie gibt eine absolute Garantie, dass ein Algorithmus bei noch so großen Problemen gut funktioniert. Experimente dagegen liefern sehr exakte Zahlenwerte für konkrete Beispielprobleme. Beides zusammen ergibt ein verlässliches und genaues Bild von der Qualität des analysierten Algorithmus.

Originalveröffentlichungen

B. Doerr, T. Friedrich, T. Sauerwald:
Quasirandom Broadcasting.
In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 773-781 (2008).
P. Erdős, A. Rényi:
The Evolution of Random Graphs.
Magyar Tudományos Akadémia Matematikai Kutató Intézeténk közleményei 5, 17–61 (1960).
Zur Redakteursansicht