Peer-to-Peer-Netzwerke: Algorithmen und Methoden

d-reguldrer Zufallsgraph mit Wahrscheinlichkeit 1 - o(1) zusammenhangend and fur hohere konstante Grade gilt der Zusammenhang mit Wahrscheinlichkeit 1 - n also mit polynomiell hoher Wahrscheinlichkeit [71].
    Es existiert auch eine einfache verteilte Operation, die in der Lage ist, ausgehend von einem beliebigen d-regularen Graphen G aus 9n.d jeden anderen Zufallsgraphen aus 9n,d schnell and mit uniformer Wahrscheinlichkeit zu erzeugen. Diese Operation nennt sich Simple Switching and wurde eingefuhrt von McKay [72] (und verwendet in [73, Seite 215] unter dem Namen Rewiring). Die Simple Switching-Operation ist wie folgt definiert:
    Definition 9.1 (Simple Switching). Sei G = (V, E) ein ungerichteter d-reguldrer Graph. Wdhle zwei Kanten {v1, v2}, {v3i v4} zuftillig and gleichwahrscheinlich aus E. Ersetze these Kanten durch Kanten {v1, v3}, {v2, v4} oder {v1, v4}, {v2, v3}, falls der resultierende Graph keine Mehrfach-Kanten besitzt.
    Zur Veranschaulichung wird die Simple Switching-Operation in Abbildung 9.8 dargestellt. In [74] wird gezeigt, dass lediglich eine polynomielle Anzahl von Simple Switching-Operationen erforderlich ist, um einen einen echt zufalligen Graph aus 9n,d zu erzeugen. Es wiederholen sich hier allerdings die Probleme, auf die wir schon bei der verteilten Umsetzung einer Operation fur Graphen des yn,p-Modells gestoBen sind. So ist es zum einen schwierig, zwei zufallige Kanten mit uniformer Wahrscheinlichkeit zu bestimmen. Zum anderen besteht immer noch die Gefahr, dass der Graph in zwei oder mehr Zusammenhangskomponenten zerfallt, wenngleich die Wahrscheinlichkeit hierfur nun deutlich geringer als zuvor ist.
    Eine andere Technik fur die Umsetzung d-regularer Zufallsnetzwerke wird in [75] vorgestellt. Wir werden diesen Ansatz jedoch nicht im Detail besprechen and betrachten im Folgenden nur die grundlegende Idee. Das Netzwerk [75] verwendet einen zentralen Host-Server, der einen Cache-Speicher mit konstant vielen zufalligen Peers im Netzwerk unterhalt. Jeder Peer, der sich neu anmeldet, wird aus diesem Cache mit zufalligen Nachbarn verbunden. Das Hauptaugenmerk des Artikels gilt der Beschreibung and Analyse der Technik, diesen konstant groBen Cache zu unterhalten. Jeder Knoten, der dem Netzwerk beitritt, erhalt eine Chance, in den Cache zu gelangen.

    Abb. 9.8. Die Simple Switching-Operation.
    Dieser Ansatz liefert eine effiziente Methode, um Zufalls-Netzwerke aufzubauen. Aber die Verwendung eines zentralen Servers steht naturlich im krassen Gegensatz zu den elementaren Grundsatzen eines Peer-to-Peer-Netzwerks, and es stellt sich die Frage, warum dieser Server nicht gleich die gesamte Knotenmenge inklusive der Kamen verwaltet. Ersetzt man den zentralen Server durch eine Reihe von Servern, so erhalt man das Aquivalent eines hybriden Netzwerks wie Fast-Track oder Gnutella-2, die wir in Kapitel 13 kennenlernen werden.
9.2.2 Ungerichtete regulare Zufallsgraphen
    Wir werden nun sehen, wie rich ein Peer-to-Peer-Netzwerk, auf Basis regularer zusammenhangender Zufallsgraphen, verteilt, d.h., ohne Zuhilfenahme zentraler Mechanismen, unterhalten lasst. Hierzu betrachten wir nicht Langer einen zufalligen Graphen aus der Masse cn,,d, sondern wir schranken uns auf die Teilmenge der zusammenhangenden Graphen aus cn.d ein. Diese Teilmenge der zusammenhangenden regularen Graphen bezeichnen wir fortan als Ccn,.d.
Die 1-Flipper Operation
    In [76] wird eine einfache verteilte Operation beschrieben, die jeden Graphen aus Ccn,,d mit uniformer Wahrscheinlichkeit generieren kann. Diese Operation wird als 1-Flipper-Operation bezeichnet and besitzt Ahnlichkeit mit der schon vorgestellten Simple Switching-Operation. Aus Graphen-theoretischer Sicht ist die 1-FlipperOperation wie folgt definiert:

    Definition 9.2 (1-Flipper). Betrachte einen ungerichteten, zusammenhangenden and d-reguldren Graphen G = (V, E) sowie vier Knoten v1, v2, v3, v4 E V, die einen Pfad P = (v1, v2, v3i v4) in G definieren. Falls {v1, v3}, {v2, v4} ~ E, dann trans- formiertdie I-Flipper-Operation FP den Graphen Gzu FP (G) = (V, E') mit

    Die 1-Flipper-Operation wird in Abbildung 9.9 veranschaulicht. Wir bezeichnen die Kamen {vi, v3}, {v2i v4} auch als Flip-Kanten and die Kante {v2, v3} als Hub- Kante der 1-Flipper-Operation.
    Abb. 9.9. Die 1-Flipper-Operation [76].
    Ein wichtiger Unterschied zwischen der 1-Flipper- and Simple Switching-Operation ist, dass die 1-Flipper-Operation den Zusammenhang des Graphen garantiert. Dies lasst sich leicht durch das