P2P Fingertables

Fehler im Skript?

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

P2P Fingertables
Hey also uns ist folgendes Problem im Skript aufgefallen mit dem Algorithmus:

RK_2_Anwendungsschicht.pdf Seite 90 enthaelt den Chord-Lookup Algorithmus, und auf Seite 91-92 stehen 2 Beispiel Lookups dazu.

Aber beide Beispiele folgen nicht dem Algorithmus:
Beispiel 1:
Bei Knoten 18 in der Fingertable geht man nach Algorithmus so vor:

(26 <= FT_p[1]) = (26 <= 20) = false (FT_p[m] <= 26) = (4 <= 26) = true

=> naechster Knoten waere 4, nicht wie im Beispiel 20.

Das selbe Spiel mit dem 2. Beispiel nur noch offensichtlicher:
Peer p = 28, Key k = 12
Algorithmus Zeile 2:
wiederhole bis p >= k:

Also terminieren wenn 28 >= 12, oops, wir sind schon fertig.

Wenn das jemand noch mal erklaeren koennte oder verifizieren ob das ein Fehler ist, waere klasse.

Gruesse,
Tempus Maximus


Wenn ich das richtig verstehe, muss man in den Algorithmus noch etwas hineininterpretieren :):

Wir haben ja einen Kreis, d.h. dass immer gelten kann, dass p >= k ist. Nun nehmen wir an, dass nach der ersten Auswahl aber p < k gilt. Dann funktioniert das 2.Beispiel schon mal.
Selbe Vorgehensweise liefert auch korrektes Verhalten für Beispiel 1.

Die Folien sind aber in der Tat etwas verwirrend dargestellt…


Vor dem Problem stande ich gestern auch.

Mit der Annahme, dass nach der esten Auswahl immer p < k gilt funktioniert der Algorithmus aber auch nicht.
Beim 2. Beispiel einfach den Peer um eins nach hinten verschieben, also Lookup von k = 12 auf Peer 21, dann hat man nach einem Schritt wieder das gleiche Problem.

Ich finde die Bedingung “Wiederhole bis p >= k” ist so nicht richtig, bei k = 0 trifft das ja immer zu egal wo ich anfange. Eigentlich muss man ja solange springen, bis man direkt hinter k ist, also k übersprungen hat.
Die nachgesellte Bedingung p_alt < k <= p_neu würde schon eher passen.
Zwar läuft man, wenn man schon am Zielpeer anfängt einmal im Kreis, aber dann ist Suchanfrage auch nutzlos.


Ich meinte damit, dass man min. 1 mal über die 0 drüber muss, sollte k schon zu Beginn <= p sein.


Ich hab da auch mal ne Frage: wenn ich p= {4, 9, 11} habe, gilt dann succ(5,6,7,8) = 9 und succ(9) = 11 oder succ(5,6,7,8,9) = 9 ? Ich habe in einer alten Lösung gesehen, dass das variiert, je nachdem, ob man grade die “normalen” Fingertabellen erstellt oder ob ein Knoten eigefügt und die Tabellen aktualisiert werden (aber nur bei i=1). Oder ist das einfach ein Fehler in der alten Lösung?

edit: Ich bin zu dumm zum Rechnen, und wies scheint war einfach die alte Lösung falsch… :wink: WIrd Zeit, dass die Klausuren rum sind, Lernen scheint mir nicht gut zu bekommen.

1 „Gefällt mir“