Peer-to-Peer-Netzwerke: Algorithmen und Methoden

als lineare Liste verket- tet. Dadurch hat sich der Suchweg im Erwartungswert halbiert, wobei die erwartete Anzahl ubersprungener Knoten Eins ist. Unter den ausgewahlten Knoten wird dieses Verfahren jetzt wiederholt, bis nur noch ein Knoten ubrig bleibt, siehe Abbildung 8.5.
    Zur Analyse werden die Knoten der ersten Liste als Ebene 0 bezeichnet. Knoten, die einmal ausgewahlt worden sind, befinden sich in Ebene 1. So befindet sich jeder Knoten, der k-mal ausgewahlt wurde, in der Liste der Ebene k. Der resultierende Graph ist die Skip-Liste. Man kann sich leicht Uberlegen, dass mit hoher Wahrscheinlichkeit, d.h. 1 - nc, die Hohe der obersten Ebene hochstens O(log n) betragt.
    Abb. 8.5. Die Skip-Liste.
    Wenn man in einer Skip-Liste sucht, dann fangt man beim vordersten Knoten in der obersten Ebene an and uberpruft, ob der angezeigte Knoten hinter dent gesuchten Datum liegt. Ist das nicht der Fall, dann folgt man den Zeigern der Ebene solange man das Ziel nicht Uberschreitet. Ist das der Fall, verringert man die Hohe and wiederholt das Verfahren in der nachsttieferen Ebene. Da man das Datum nie Uberspringt, wird man spatestens in der Ebene 0 erfolgreich sein.
    Dieser Suchalgorithmus ist Behr effizient: Man kann zeigen, dass in jeder Ebene erwartungsgemaB hochstens zwei Schritte durchgefuhrt werden. Somit kann in erwarteter Suchzeit von O(log n) jedes Datum gefunden werden. AuBerdem ist der erwartete zusatzliche Platzverbrauch fur these Datenstruktur O(n). Ferner ist sowohl der Eingrad als auch der Ausgrad des Graphen mit hoher Wahrscheinlichkeit O(log n).
    Statt die Hohe der Elemente zufallig zu wahlen, kann man auch einen deterministischen Algorithmus verwenden. Dieser weist jedem Element eine Hohe zu, die der Anzahl der Nullen am Ende der Binardarstellung der Ordnungszahl entspricht. Im Gegensatz zu der randomisierten Wahl kann man these Darstellung beim EinfUgen neuer Datenelemente jedoch nicht aufrecht erhalten. Bei der randomisierten Wahl werden fur das neue Element einfach Munzwurfe wiederholt, bis die Hohe bestimmt worden ist, and dann wird das Element entsprechend eingef igt.

8.2.2 Skip-Graph
    Eine Skip-Liste eignet sich nicht als Verbindungsstruktur fur ein Peer-to-Peer-Netzwerk, da der Verlust derjenigen Peers, die Knoten groBer Hohe entsprechen, unweigerlich zur Partitionierung des Netzwerks fuhren wurde. Es wird also eine Datenstruktur angestrebt, die, ahnlich wie Skip-Listen, eine effiziente Suche ermoglicht, aber keine strukturellen Schwachpunkte erzeugt.
    Hierzu stellt man sich vor, dass die Peers die Rolle der Daten aus der einfach verketteten Liste wahrnehmen. Diese ist bier doppelt verkettet, die Ordnung bleibt aber erhalten. Wie bei der Skip-Liste wirft man jetzt fur jeden Peer eine MUnze mit Ergebnis 0 oder 1. Die Gewinner bilden wieder eine neue sortierte Liste, siehe Abbildung 8.6. Nun erlaubt man aber auch den Verlierern, eine eigene sortierte Liste zu bilden. In den beiden disjunkten Listen dieser Ebene wird dieses Verfahren jetzt iteriert, bis nur noch einzelne Peers ubrigbleiben, siehe Abbildung 8.7.
    Im ursprunglichen Artikel [50] waren die einzelnen Listen, ahnlich wie die SkipListe, offen. Seit [51] werden das erste and das letzte Element der einzelnen Listen verbunden, da dadurch die Robustheit der Liste ohne Zusatzaufwand erhoht wird. Es entsteht die baumformige Struktur aus der Abbildung 8.8.
    In Skip-Graphen gibt es nun zwei Methoden der Adressierung: Den Name-ID genannten Schlussel eines Peers, welcher die Sortierung in der einfachen Liste definiert, and die Folge der Zufallsbits Num-ID (Numeric Identification), welche die Zugehorigkeit in den einzelnen Teilmengen angeben. Man kann sich vorstellen, dass these Folge Langer als die Hohe des entsprechenden Teilzweigs ist.

    Daraus folgt, dass der Eingrad and der Ausgrad eines Skip-Graphen mit hoher Wahrscheinlichkeit hochstens O (lo; n) ist. Damit ist auch der Durchmesser maximal O(log n). Skip-Graphen sind auBerdem sehr robust gegen Knotenausfalle (highly resilient). Das folgt insbesondere aus der Expandereigenschaft von Skip-Graphen [52].
Skip-Net
    Wie bereits erwahnt, unterscheiden wir hier Skip-Graphen and Skip-Nets nur darin, ob wir den Graphen oder das zugehorige Peer-to-Peer-Netzwerk betrachten. Die Knoten des Skip-Nets sind die Peers. Kamen stehen in der Routing-Tabelle der Peers. Jeder Peer erhalt so zwei Adressen: Die Name-ID and die Num-ID.

    Abb. 8.6. Autbau eines Skip-Graphen.

    Abb. 8.7. Ein vollstandiger Skip-Graph.
    Abb.