Student | (visible for staff only) |
Supervisor | Dr. Sebastian Schildt |
Professor | Prof. Dr.-Ing. Lars Wolf |
Project | LocCom |
IBR Group | CM (Prof. Wolf) |
Type | Master Thesis |
Status | finished |
MotivationViele Anwendungen erfordern es, zwei Sets von Daten zwischen zwei Geräten zu synchronisieren. Beispiele sind die Filesynchronisation bei inkrementellen Backup-Systemen oder die Synchronisierung von Datenbanken und verteilten Filesystemen oder auch der Abgleich der Bundle Storages von zwei DTN Knoten. Hierbei ist das Differenzset zwischen zwei Mengen zu bestimmen, um herauszufinden welche Elemente des einen Set im anderen nicht vorhanden sind. Dieses Problem ist als Set Reconcillation bekannt. Da eine Liste aller Elemente bei großen Sets sehr umfangreich ist, existieren effizientere approximative Methoden, wie zum Beispiel Bloom Filter, um Elemente des Differenzsets zu bestimmen. Viele Anwendungen können jedoch Fehler, die durch approximative Methoden entstehen, nicht tolerieren sondern benötigen fehlerlose Verfahren. Interessant sind daher Set Reconcillation Methoden die deterministisch sind, zustandslos (stateless) arbeiten und dabei dennoch effizient sind: Eine Voraussetzung hierbei ist, dass nichts über das Set des Kommunikationspartners bekannt sein muss, um einen Abgleich durchzuführen. Bei zustandsbehafteten Synchronisationen, die z.B. auf der Übertragung von Inkrementen beruhen, muss der Zustand des Gegenübers stets bekannt sein. Zustandslose Synchronisationsverfahren haben diesen Nachteil nicht und eignen sich daher zum Beispiel um zustandsbehaftete Synchronisationsverfahren zu starten (Bootstrapping), oder um einen konsistenten Zustand herzustellen, wenn Fehler aufgetreten sind. AufgabenstellungIn dieser Arbeit soll eine generische Library zum Abgleich zweier Sets auf Basis der um einen Trie erweiterten Bloom Filter erstellt werden. Folgende generelle Anforderungen bestehen an die Library:
Die Library soll in einer bestehenden Anwendung eingesetzt werden oder diese ersetzen. Der erreichte Kommunikationsoverhead ist mit der ursprünglichen Anwendung zu vergleichen. Zu möglichen Einsatzszenarien der Library ist eine Analyse anzufertigen. Hierbei können zum Beispiel Wege angedeutet werden, wie man den Mechanismus erweitern müsste, wenn es sich bei den zu synchronisierenden Sets um Daten handelt, deren Inhalt sich bei gleicher Identität ändert, oder Elemente die komplex strukturierte Metadaten enthalten (File Synchronisation). Ebenfalls erwähnenswert sind Anwendungsfälle wo es nicht um das Differenzset, sondern um die Schnittmenge geht, wie beispielsweise bei der Deduplikation von Daten. |
Vacancies of TU Braunschweig
Career Service' Job Exchange
Merchandising
Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard
Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig
P. O. Box: 38092 Braunschweig
GERMANY
Phone: +49 (0) 531 391-0