Peer-to-Peer-Netzwerke: Algorithmen und Methoden

bei Verwendung gerichteter Graphen: Um eine Kante in einem gerichteten Graphen zu andern, muss lediglich detjenige Knoten, der den Startpunkt der Kante definiert, den Zielpunkt in seiner Nachbarschaftsliste andern. Stellt dieser Graph nun ein Netzwerk dar, bedeutet dies, dass das Andern einer Kante nur noch eine lokale Operation ist and keine teure Kommunikation im Netzwerk stattfinden muss. Wenn wir also eine ahnliche Operation fur gerichtete Graphen mit regularem Ausgrad linden, konnen wir unter Umstanden die Anzahl der Kommuni- kationsschritte je Operation deutlich verringern.
    Wir uberlegen uns zunachst, welche grundlegenden Moglichkeiten es gibt, die Kanten eines gerichteten Graphen G = (V, E) zu andern. Betrachten wir einen Knoten vl E V, so gibt es zwei prinzipielle Moglichkeiten, die durch die beiden folgenden Operationen beschrieben werden:
    Pointer-Push: Verandere die Menge der ausgehende Kanten von vj, d.h., fuhre einen Random Walk vt, v2, v3 in G durch and ersetze die Kante (vt, v2) durch die Kante (V 1, v3) (siehe Abbildung 9.10).
    Pointer-Pull: Verandere die Menge der auf vl zeigenden Kanten, d.h., fuhre einen Random Walk vl, v2, v3, v4 in G durch and ersetze die Kante (v3i v4) durch die Kante (v3i V) (siehe Abbildung 9.11).
    Abb. 9.10. Die Pointer-Push-Operation.
    Die Einfachheit dieser elementaren Operationen bringt mit sick, dass die resultierenden Graphen gerichtete Multi-Graphen sein konnen, d.h., Kanten konnen mehr fach existieren and Knoten konnen auf Bich selbst zeigen. Dies lieBe sich sicherlich durch einfache Abfragen beheben, wir werden spater in diesem Kapitel jedoch noch sehen, dass wir Multi-Kanten tatsachlich benotigen. Deshalb betrachten wir von nun an gerichtete zusammenhangende Multigraphen mit regularem Ausgrad and bezeichnen die Menge dieser Graphen als .MDcn,d. Auch hier benennt n wieder die Anzahl der Knoten and d den Ausgrad ebendieser.

    Bei naherer Analyse der beiden elementaren Operationen zeigt sich jedoch, dass weder Pointer-Push- noch Pointer-Pull-Operation tatsachlich fur die Unterhaltung zufalliger Graphen aus .MDcn,d geeignet sind. Zwar behalt der Graph G in beiden Fallen seinen regularen Ausgrad d, im Fall der Pointer-Push-Operation konnen jedoch Schleifen an einem Knoten erzeugt werden. Dies geschieht, wenn der StartKnoten der Operation auch der End-Knoten der Operation ist. Genau das wird problematisch, wenn alle ausgehenden Kanten eines Knotens v Schleifen sind. Diese Schleifen konnen dann nicht mehr durch Pointer-Push-Operationen entfernt werden. Gleiches gilt dann fur Kanten, die auf v zeigen. Der Knoten v wirkt dann wie eine Senke and wird im Laufe der Zeit immer mehr Kanten an sich ziehen. So wird der Graph G durch wiederholtes Anwenden der Pointer-Push-Operation zu einem sternformigen Graphen oder im Fall mehrerer Senken zu einer Menge verbundener Sterne konvergieren (siehe Abbildung 9.12). Ein solcher Graph wird sich auch durch weitere Pointer-Push-Operationen nicht mehr verandern.
    Im Fall der Pointer-Pull-Operation ist leicht zu sehen, dass these nicht den Zusammenhang des Graphen garantiert. So wurde ein Graph G durch wiederholtes Anwenden dieser Operation zu einem Graphen aus Tauter einzelnen Knoten mit Schleifen transformiert (siehe Abbildung 9.13). Bei genugend hohem Grad kann es zwar sehr lange dauern, bis der Graph tatsachlich nicht mehr zusammenhdngend ist, da das Auseinanderfallen in einem Netzwerk jedoch irreversibel ist, disqualifiziert dies die Pointer-Pull-Operation fur den praktischen Einsatz.
    So sind beide Elementaroperationen nicht fur die Unterhaltung gerichteter Zufallsnetzwerke geeignet. Wir werden im folgenden Abschnitt jedoch sehen, dass eine Kombination dieser Operationen die beschriebenen Probleme beheben kann.
    Abb. 9.11. Die Pointer-Pull-Operation.

    Abb. 9.12. Beim wiederholten Anwenden von Pointer-Push-Operationen konvergiert ein Graph gegen einen sternformigen Multi-Graphen.
    Abb. 9.13. Wiederholtes Anwenden von Pointer-Pull-Operationen zerlegt einen Graphen in einzelne Knoten mit Schleifen.
Die Pointer-Push&Pull-Operation
    Eine geschickte Kombination von Pointer-Push- and Pointer-Pull-Operation wird in [77] vorgestellt. Diese Operation wird als Pointer-Push &Pull bezeichnet and ist formal wie folgt definiert:
    Definition 9.6 (Pointer-Push&Pull). Sei G = (V, E), G E .MDc,,d, ein gerichteter and zusammenhdngenderMulti-Graph mit reguldremAusgrad d. Seien des Weiteren vt, v2, V3 E V Knoten, die einen gerichteten Pfad P = (vt, V2, V3)