@inproceedings{KruberLangeSchintke, author = {Kruber, Nico and Lange, Maik and Schintke, Florian}, title = {Approximate Hash-Based Set Reconciliation for Distributed Replica Repair}, series = {2015 IEEE 34th International Symposium on Reliable Distributed Systems (SRDS)}, booktitle = {2015 IEEE 34th International Symposium on Reliable Distributed Systems (SRDS)}, publisher = {IEEE}, doi = {10.1109/SRDS.2015.30}, pages = {166 -- 175}, language = {en} } @misc{Lange, type = {Master Thesis}, author = {Lange, Maik}, title = {Effiziente Reparatur von Repliken in Distributed Hash Tables}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42275}, school = {Zuse Institute Berlin (ZIB)}, abstract = {Eine distributed hash Table (DHT) stellt eine {\"u}ber multiple Rechner strukturiert verteilte Tabelle von Schl{\"u}ssel-Wert-Paaren dar. Ein verteiltes System unterliegt zumeist einer Teilnehmerdynamik in Form von ausfallenden oder beitretenden Knoten, wodurch Daten verloren gehen k{\"o}nnen. Zur Sicherstellung der Verf{\"u}gbarkeit aller Schl{\"u}ssel-Wert-Paare ist Redundanz notwendig. Die Einf{\"u}hrung einer Redundanzschicht erh{\"o}ht die Verf{\"u}gbarkeit der Daten erheblich auf Kosten einer verringerten Leistungsf{\"a}higkeit. Der Fokus dieser Arbeit liegt im Erhalt der Redundanz, was die Regeneration verlorener Kopien sowie eine Aktualisierung veralteter Kopien umfasst. Die Regeneration verlorener Kopien ist notwendig um die Verf{\"u}gbarkeit langfristig zu sichern. Die Aktualisierung ist optional und verbessert die Leselatenz in geografisch weit verteilten Systemen. Die vorgestellte L{\"o}sung besteht aus drei Komponenten. Der Set Reconciliation Dienst erm{\"o}glicht den effizienten Vergleich zweier Knoten zur Identifikation verlorener und veralteter Kopien. Der Aktualisierungsdienst synchronisiert die verglichenen Knoten durch die {\"U}bertragung der Differenzen. Die dritte Komponente ist ein Anti-Entropie Protokoll, dass die Auswahl eines jeden Knotens als Synchronisationspartner sicherstellt. Das Ziel dieser Arbeit liegt in dem Vergleich dreier Set Reconciliation Algorithmen, deren Eignung und Leistungsf{\"a}higkeit f{\"u}r die Erkennung verlorener und veralteter Kopien evaluiert werden soll. Ausgew{\"a}hlt wurden der Bloom Filter, der Merkle-Tree sowie deren Kombination der Approximate Reconciliation Tree. Die Evaluation zeigte, dass der Merkle-Tree die h{\"o}chste Genauigkeit besitzt und sp{\"a}testens nach einer initiierten Synchronisation eines jeden Knotens zur vollst{\"a}ndigen Synchronit{\"a}t in der DHT f{\"u}hrt. Der Bloom Filter besitzt bei der Erkennung verlorener Repliken nur die halbe Genauigkeit gegen{\"u}ber veralteten Repliken, wodurch die Konvergenzgeschwindigkeit dementsprechend geringer ist gegen{\"u}ber dem Merkle-Tree. Daf{\"u}r sind die {\"U}bertragungskosten des Bloom Filter um bis zu 80\% geringer als beim Merkle-Tree und weisen kaum nennenswerte Spitzen auf. Die {\"U}bertragungskosten des Merkle-Tree sind abh{\"a}ngig von der Anzahl der Differenzen, sodass bei einer Differenz von Null nur eine Signatur mit weniger als einem kByte {\"u}bertragen werden muss. Ist die Differenz gr{\"o}ßer, steigen die Kosten je nach Bucket-Gr{\"o}ße an. Der Approximate Reconciliation Tree ist ein als Bloom Filter codierter Merkle-Tree, der je nach Parameterkonstellation die Eigenschaften einer der beiden Strukturen aufweist. Die Bloom Filter {\"a}hnlichen Konfigurationen bieten keinen Vorteil, wohingegen die Merkle-Tree {\"a}hnlichen nur zwei Mitteilungsrunden ben{\"o}tigen bei einer leichten Genauigkeitsverringerung gegen{\"u}ber dem Merkle-Tree.}, language = {de} }