Peer-to-Peer-Netzwerke: Algorithmen und Methoden

in G bilden. Dann transformiert die Pointer-Push &Pull- Operation PPP den Graphen G zum Graphen PPP (G) = (V, E'), wobei

    Die Pointer-Push&Pull-Operation wird in Abbildung 9.14 dargestellt. Anhand der Abbildung lasst sich leicht sehen, dass these Operation vom Prinzip her einer Pointer-Pull-Operation zwischen den Knoten vl and V2 and einer Pointer-PushOperation zwischen den Knoten vi and V3 entspricht.
    Wird these Operation wiederholt auf zufallige Pfade im Graphen angewendet, so hat sie vergleichbare Eigenschaften wie die 1-Flipper-Operation. Es ist allerdings noch festzulegen, wie der Random Walk einer Pointer-Push&Pull-Operation durchgefuhrt wird. Am sinnvollsten ist es, in jedem Schritt einer zufalligen der d Kamen eines Knotens zu folgen. Wir bezeichnen dies als kantenorientierten Random Walk. Alternativ konnte bei einem knotenorientierten Random Walk in jedem Schritt einer der hochstens d Nachbarknoten gewahlt werden.

    Kommen wir zuruck zu den Eigenschaften der Pointer-Push&Pull-Operation. Angewendet auf einen Graphen G E .MDc,z,d, bewahrt sie offenbar den Zusammenhang von G, da alle beteiligten Knoten miteinander verbunden bleiben. Weiterhin ist die Operation symmetrisch2, d.h., fur Graphen G, G' E MDc,z,d gilt

    Da auch jeder Graph G E MDc,z,d durch eine Folge von Pointer-Push&PullOperationen erreicht werden kann, gilt - ahnlich zur I-Flipper Operation - folgendes Theorem:
    Theorem 9.7. Sei G' E MDc,,,d ein beliebiger zusammenhdngender gerichteter Multi-Graph mit reguldrem Ausgrad d. Dann wird durch wiederholtes Anwenden zufdlliger Pointer-Push &Pull- Operationen mit knotenorientiertem Random Walk im Limes jeder Graph G E .MDc,,,d mit der gleichen Wahrscheinlichkeit erzeugt, d.h.,

    Die Pointer-Push&Pull-Operation erzeugt also echt zufallige Graphen aus der Menge .MDg,,d. Wird anstelle des knotenorientierten Random Walk ein kantenorienter Random Walk verwendet, so werden die Graphen aus .MDc,,,,d nicht mehr mit uniformer Wahrscheinlichkeit erzeugt, sondern Graphen aus .MDc,z,d mit wenig oder keinen Multi-Kanten, and Schleifen treten mit etwas hoherer Wahrscheinlichkeit auf (fur Details siehe [77]).
    Abb. 9.14. Die Pointer-Push&Pull-Operation

    Betrachten wir nun die Umsetzung der Pointer-Push&Pull-Operation in einem Peer-to-Peer-Netzwerk. Jeder Peer wird zu zufalligen Zeitpunkten eine PointerPush&Pull-Operation initiieren. Sei pl dieser Peer. Der Ablauf der Operation geschieht dann in drei Schritten:
    Schritt I.- Peer pt kontaktiert einen zufalligen Peer p2 seiner Nachbarschaftsliste and teilt ihm den Beginn der Operation mit.
    Schritt 2: Peer p2 empfangt die Nachricht von pt and wahlt einen zufalligen Peer p3 aus seiner Nachbarschaftsliste. Weiterhin ersetzt p2 den Eintrag p3 durch pt an der entsprechenden Stelle in seiner Nachbarschaftsliste and sendet als Antwort die Adresse des Peers p3 zuruck an pl.
    Schritt 3: Peer pt empfangt die Antwort von p2 and ersetzt seinerseits den Eintrag P2 durch p3 in seiner Nachbarschaftsliste.
    Innerhalb dieser drei Schritte werden lediglich zwei Nachrichten zwischen den Peers pt and P2 ausgetauscht. Des Weiteren enthalten these Nachrichten lediglich die Adresse eines Peers. Somit ist eine Pointer-Push&Pull-Operation vom Kommunikationsaufwand nicht teurer als die in dynamischen Netzwerken obligatorische pe- riodische Uberpri fung der Nachbarschaft. Ferner lasst sich die Pointer-Push&PullOperation mit dieser Uberprufung kombinieren, so dass letztendlich kein oder kaum zusatzlicher Netzwerkverkehr entsteht.
    Auch das Einf igen and Entfernen von Peers in gerichteten Multi-Graphen mit regularem Ausgrad gestaltet sich viel einfacher als im Fall von ungerichteten Graphen. Tritt ein neuer Peer dem Netzwerk bei, so reicht es im Prinzip, wenn er einen Peer in seine Nachbarschaftsliste aufnimmt and diesen Eintrag d - 1-mal dupliziert. Dutch Anwenden der Pointer-Push&Pull-Operation wird dennoch ein zufalliges Netzwerk entstehen. Auch wenn ein Peer ohne Vorankundigung ausfallt, lasst sich das einfach losen. Sobald ein Nachbar sich als tot herausstellt, wird dieser mit der Kopie eines anderen Eintrags der Nachbarschaftsliste ersetzt. Wieder wird eine Folge von Pointer-Push&Pull-Operationen beim simultanen Ausfall vieler Peers entstehende Probleme bereinigen.
    Simulationen legen nahe, dass sowohl die 1-Flipper-Operation als auch die Pointer-Push&Pull-Operation schnell zur uniformen Wahrscheinlichkeitsverteilung konvergiert. Schnell heiBt hier, dass O(dn log n) parallele verteilte