Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Betrachten der Abbildungen 9.9 and 9.8 feststellen: Im Fall der 1-Flipper-Operation bleiben alle beteiligten Knoten miteinander verbunden, im Fall von Simple Switching jedoch nicht.
    Wir werden nun sehen, dass, ausgehend von einem beliebigen d-regularen, zusammenhangenden Graph mit n Knoten, jeder andere Graph aus Cc,,,,d durch wiederholtes Anwenden zufalliger 1-Flipper-Operationen mit uniformer Wahrscheinlichkeit erzeugt wird. Zufallige 1-Flipper-Operation bedeutet hierbei, dass der Pfad P zufallig gewahlt wird, d.h., es wird ausgehend von einem zufalligen Startknoten ein Random Walk uber drei Kamen durchgefuhrt. Werden bei diesem Random Walk nicht vier unterschiedliche Knoten besucht, wird die Operation abgebrochen.
    Um nun zu zeigen, dass die 1-Flipper-Operation Graphen aus Cc",d uniform generiert, betrachten wir zunachst einige wichtige Eigenschaften der Operation.
    Lemma 9.3. Die Wahrscheinlichkeit, dass ein d-reguldrer Graph G durch eine zufallige I-Flipper-Operation zu einem d-reguldren Graphen G' transforiniert wird, ist identisch mit der Wahrscheinlichkeit, dass G' durch eine zufallige I-FlipperOperation zu G transformiert wird. Das heif3t, es gilt

    Diese Eigenschaft der 1-Flipper-Operation bezeichnen wir auch als Symmetric. Der Beweis des Lemmas ist nicht schwierig and wird hier nicht gefuhrt. Er kann in [76] nachgelesen werden. Eine weitere Grundvoraussetzung fur die uniforme Ge- nerierung von Graphen aus Ccn,d liefert das folgende Lemma:
    Lemma 9.4. Fur alle Paare G, G' von Graphen aus Ccn,d mit d > 2 and d gerade, existiert eine Folge von I -Flipper-Operationen, die G zu G' transformiert.
    Diese Eigenschaft bezeichnen wir auch als Erreichbarkeit, da jeder Graph aus Ccn,d zujedem anderen aus Ccn,d transformiert werden kann. Kombiniert man nun die Aussagen von Lemma 9.3 and Lemma 9.4, folgt bereits die Eigenschaft, dass eine Folge von 1-Flipper-Operationen auf Lange Sichtjeden Graphen aus CCj- n,d mit der gleichen Wahrscheinlichkeit erzeugt. Um dies zu sehen, betrachten wir den Markov- Prozess, den die 1-Flipper-Operation uber den Graphen aus Ccn,d beschreibt. Jeder Graph aus Ccn,d entspricht einem Zustand dieses Markov-Prozesses. Lemma 9.3 besagt, dass die zugehorige Markov-Matrix symmetrisch ist, and Lemma 9.4 zeigt, dass jeder Zustand des Markov-Prozesses erreichbar ist. Elementare Markov- Prozesstheorie besagt nun, dass im Limes jeder Startvektor gegen den uniformen Vektor mit gleichen Eintragen konvergiert, welcher der uniformen Wahrscheinlichkeitsverteilung entspricht. Wir halten dieses Ergebnis im folgenden Theorem test.
    Theorem 9.5. Sei G ein d-regularer zusammenhangender Graph mit n Knoten and d > 2 and d gerade. Dann wird durch wiederholtes Anwenden von zufalligen I- Flipper-Operationen jeder d-regulare zusammenhangende Graph mit n Knoten mit gleicher Wahrscheinlichkeit erzeugt, d.h.,

    Die 1-Flipper-Operation kann ohne weiteres verteilt angewendet werden, wenn die Menge der Peers gleich bleibt oder wachst (und der Grad gerade ist). Kommt ein Peer hinzu, so bestimmt er d/2 knotendisjunkte Kamen, loscht these and setzt eine Kante zu jedem der d Endpunkte. So bleibt das Netzwerk d-regular and zusammenhangend. Schwieriger wird es, wenn ein Peer das Netzwerk verlasst bzw. ausfallt and somit bei seinen d Nachbarn den Grad d - 1 erzeugt. Diese Nachbarn mussten sich jetzt auf die Suche nach anderen Peers mit demselben Problem machen. Das ist aber in einem unstrukturierten Netzwerk sehr aufwandig. Eine einfache Losung fur das Problem ist, wenn Peers mit zu geringem Grad diesen erst dann erhohen, wenn ihnen mindestens zwei Nachbarn fehlen. In dem Fall kann dann einfach wie beim Einfugen eines neuen Peers vorgegangen werden, d.h., der Peer setzt sich in die Mitte einer zufalligen Kante des Netzwerks. Dieses Vorgehen hat zur Folge, dass die resultierenden Graphen bzw. Netzwerke zwar nicht mehr exakt d-regular sind, die Grade der Knoten liegen jedoch immer zwischen d and d - 1, was in der Praxis nicht weiter tragisch ist.

9.2.3 Gerichtete Zufallsgraphen mit regularem Ausgrad
    Die im vorigen Abschnitt beschriebene 1-Flipper-Operation ist bereits sehr gut geeignet, um Zufalls-Netzwerke zu unterhalten. Aus praktischer Sicht lasst sich these Operation jedoch noch weiter verbessern. Ansatzpunkt fur die Verbesserung sind die ungerichteten Kanten. Um eine ungerichtete Kante zu unterhalten and ggf. zu andern mussen immer beide zu dieser Kante adjazenten Knoten miteinander kommunizieren. Dieser Aufwand entfallt