Show simple item record

2020-04-24Dissertation DOI: 10.18452/21294
Approximate Distributed Set Reconciliation with Defined Accuracy
dc.contributor.authorKruber, Nico
dc.date.accessioned2020-04-24T08:28:29Z
dc.date.available2020-04-24T08:28:29Z
dc.date.issued2020-04-24none
dc.identifier.urihttp://edoc.hu-berlin.de/18452/22105
dc.description.abstractMit aktuell vorhandenen Mitteln ist es schwierig, objektiv approximative Algorithmen zum Mengenabgleich gegenüberzustellen und zu vergleichen. Jeder Algorithmus kann durch unterschiedliche Wahl seiner jeweiligen Parameter an ein gegebenes Szenario angepasst werden und so zum Beispiel Bandbreiten- oder CPU-optimiert werden. Änderungen an den Parametern gehen jedoch meistens auch mit Änderungen an der Genauigkeit bei der Erkennung von Differenzen in den teilnehmenden Mengen einher und behindern somit objektive Vergleiche, die auf derselben Genauigkeit basieren. In dieser Arbeit wird eine Methodik entwickelt, die einen fairen Vergleich von approximativen Algorithmen zum Mengenabgleich erlaubt. Dabei wird eine feste Zielgenauigkeit definiert und im Weiteren alle die Genauigkeit beeinflussenden Parameter entsprechend gesetzt. Diese Methode ist universell genug, um für eine breite Masse an Algorithmen eingesetzt zu werden. In der Arbeit wird sie auf zwei triviale hashbasierte Algorithmen, einem basierend auf Bloom Filtern und einem basierend auf Merkle Trees angewandt, um dies zu untermauern. Im Vergleich zu vorherigen Arbeiten zu Merkle Trees wird vorgeschlagen, die Größe der Hashsummen dynamisch im Baum zu wählen und so den Bandbreitenbedarf an die gewünschte Zielgenauigkeit anzupassen. Dabei entsteht eine neue Variante des Mengenabgleichs mit Merkle Trees, bei der sich erstmalig die Genauigkeit konfigurieren lässt. Eine umfassende Evaluation eines jeden der vier unter dem Genauigkeitsmodell angepassten Algorithmen bestätigt die Anwendbarkeit der entwickelten Methodik und nimmt eine Neubewertung dieser Algorithmen vor. Die vorliegenden Ergebnisse erlauben die Auswahl eines effizienten Algorithmus für unterschiedliche praktische Szenarien basierend auf einer gewünschten Zielgenauigkeit. Die präsentierte Methodik zur Bestimmung passender Parameter, um für unterschiedliche Algorithmen die gleiche Genauigkeit zu erreichen, kann auch auf weitere Algorithmen zum Mengenabgleich angewandt werden und erlaubt eine objektive, allgemeingültige Einordnung ihrer Leistung unter verschiedenen Metriken. Der in der Arbeit entstandene neue approximative Mengenabgleich mit Merkle Trees erweitert die Anwendbarkeit von Merkle Trees und wirft ein neues Licht auf dessen Effektivität.ger
dc.description.abstractThe objective comparison of approximate versioned set reconciliation algorithms is challenging. Each algorithm's behaviour can be tuned for a given use case, e.g. low bandwidth or computational overhead, using different sets of parameters. Changes of these parameters, however, often also influence the algorithm's accuracy in recognising differences between participating sets and thus hinder objective comparisons based on the same level of accuracy. We develop a method to fairly compare approximate set reconciliation algorithms by enforcing a fixed accuracy and deriving accuracy-influencing parameters accordingly. We show this method's universal applicability by adopting two trivial hash-based algorithms as well as set reconciliation with Bloom filters and Merkle trees. Compared to previous research on Merkle trees, we propose to use dynamic hash sizes to align the transfer overhead with the desired accuracy and create a new Merkle tree reconciliation algorithm with an adjustable accuracy target. An extensive evaluation of each algorithm under this accuracy model verifies its feasibility and ranks these four algorithms. Our results allow to easily choose an efficient algorithm for practical set reconciliation tasks based on the required level of accuracy. Our way to find configuration parameters for different, yet equally accurate, algorithms can also be adopted to other set reconciliation algorithms and allows to rate their respective performance in an objective manner. The resultant new approximate Merkle tree reconciliation broadens the applicability of Merkle trees and sheds some new light on its effectiveness.eng
dc.language.isoengnone
dc.publisherHumboldt-Universität zu Berlin
dc.rights(CC BY-SA 4.0) Attribution-ShareAlike 4.0 Internationalger
dc.rights.urihttps://creativecommons.org/licenses/by-sa/4.0/
dc.subjectVerteilte Systemeger
dc.subjectMengenabgleichger
dc.subjectApproximative Algorithmenger
dc.subjectGenauigkeitsmodelleger
dc.subjectMerkle Treeger
dc.subjectBloom Filterger
dc.subjectSynchronisationger
dc.subjectReplikationger
dc.subjectDistributed Systemseng
dc.subjectSet Reconciliationeng
dc.subjectApproximate Algorithmseng
dc.subjectAccuracy Modelseng
dc.subjectMerkle Treeeng
dc.subjectBloom Filtereng
dc.subjectSynchronisationeng
dc.subjectReplicationeng
dc.subject.ddc000 Informatik, Informationswissenschaft, allgemeine Werkenone
dc.titleApproximate Distributed Set Reconciliation with Defined Accuracynone
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-110-18452/22105-6
dc.identifier.doihttp://dx.doi.org/10.18452/21294
dc.date.accepted2019-11-01
dc.contributor.refereeReinefeld, Alexander
dc.contributor.refereeSchweikardt, Nicole
dc.contributor.refereeAndrzejak, Artur
local.edoc.pages196none
local.edoc.type-nameDissertation
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultätnone

Show simple item record