@misc{Prollius2009, type = {Master Thesis}, author = {Prollius, Christian von}, title = {Ein Peer-to-Peer System mit Bereichsabfragen in PlanetLab}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11492}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {Aktuelle Entwicklungen zeigen, dass Peer-to-Peer (P2P) Anwendungen wie Skype oder Bittorrent im Internet immer mehr an Bedeutung gewinnen. In den letzten Jahren hat es einen explosionsartigen Anstieg an Nutzern und Daten in solchen Netzen gegeben. Dabei stellt der eigentliche Dateitransfer zwischen zwei Rechnern kein großes Problem mehr dar und auch der Speicherbedarf f{\"u}r die große Menge an Daten kann durch die Weiterentwicklung der Hardware gut gedeckt werden. Das eigentliche Problem liegt vielmehr darin, den Rechner zu finden, der die gew{\"u}nschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ung{\"u}nstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen m{\"u}ssen, sind einerseits sehr anf{\"a}llig gegen{\"u}ber Angriffen und Ausf{\"a}llen (Single Point of Failure)und kommen auch nicht mit der st{\"a}ndig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten L{\"o}sungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale L{\"o}sungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gel{\"o}st, jedoch haben sie starke Nachteile bei der Suche nach Keys. Bei einer Suche wird ein Broadcast verwendet (jeder schickt die Anfrage an jeden weiter) und damit ein enormer Netzwerkverkehr erzeugt. In "Why Gnutella Can't Scale. No, Really" wird erkl{\"a}rt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zus{\"a}tzlich eine L{\"o}sung ben{\"o}tigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden k{\"o}nnen. Aus diesem Grund besch{\"a}ftigt sich die folgende Arbeit mit einer v{\"o}llig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endger{\"a}te den Hauptteil des Dienstes selbst erbringen und damit jeder zus{\"a}tzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit pr{\"a}sentiert Chord\#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord\# wurde ausgew{\"a}hlt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht m{\"o}glich, da dieser eine Hashfunktion f{\"u}r die Keys verwendet und somit die Daten zwar gleichm{\"a}ßig aber unsortiert auf die Teilnehmer verteilt. Es wird in dieser Arbeit gezeigt, dass mit Hilfe von Chord\# auch ohne die Hashfunktion gute Ergebnisse erzielt werden. Außerdem k{\"o}nnen durch den Verzicht auf die Hashfunktion Bereichsabfragen erm{\"o}glicht werden. Daf{\"u}r wird der Chord\# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausf{\"u}hrlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet.}, language = {de} } @misc{Plantikow2007, type = {Master Thesis}, author = {Plantikow, Stefan}, title = {Transaktionen f{\"u}r verteilte Wikis auf strukturierten Overlay Netzwerken}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10176}, school = {Zuse Institute Berlin (ZIB)}, year = {2007}, abstract = {Die Diplomarbeit pr{\"a}sentiert ein Transaktionsverfahren f{\"u}r strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen f{\"u}r verteilte Wikis betrachtet, die moderne Funktionalit{\"a}ten, wie Metadaten und zus{\"a}tzliche Indexe f{\"u}r die Navigation, unterst{\"u}tzen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausf{\"a}llen. Die Arbeit schl{\"a}gt daf{\"u}r das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verf{\"u}gbarkeit zu gew{\"a}hrleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenl{\"a}ufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausf{\"u}hrung von Nur-Lese-Transaktionen erm{\"o}glichen. F{\"u}r die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenl{\"a}ufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexit{\"a}t verglichen.}, language = {de} } @misc{Plantikow2007, author = {Plantikow, Stefan}, title = {Transaktionen f{\"u}r verteilte Wikis auf strukturierten Overlay-Netzwerken}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10466}, number = {07-43}, year = {2007}, abstract = {Die Arbeit pr{\"a}sentiert ein Transaktionsverfahren f{\"u}r strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen f{\"u}r verteilte Wikis betrachtet, die moderne Funktionalit{\"a}ten, wie Metadaten und zus{\"a}tzliche Indexe f{\"u}r die Navigation, unterst{\"u}tzen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausf{\"a}llen. Die Arbeit schl{\"a}gt daf{\"u}r das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verf{\"u}gbarkeit zu gew{\"a}hrleisten. Das Transaktionsverfahren baut darauf auf und verwendet Two-Phase-Commit mit Fehlererkennung und Widerherstellung von ausgefallenen Transaktionsmanagern. Anwendungen wird eine Auswahl an pessimistischen und hybrid-optimistischen Nebenl{\"a}ufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausf{\"u}hrung von Nur-Lese-Transaktionen erm{\"o}glichen. F{\"u}r die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenl{\"a}ufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexit{\"a}t verglichen.}, language = {de} } @masterthesis{Borgers2012, type = {Bachelor Thesis}, author = {Borgers, Philipp}, title = {Erweiterung eines verteilten Key-Value-Stores (Riak) um einen r{\"a}umlichen Index}, year = {2012}, language = {de} } @misc{Lange2012, 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)}, year = {2012}, 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} } @misc{Keidel2013, type = {Master Thesis}, author = {Keidel, Stefan}, title = {Snapshots in Scalaris}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42282}, school = {Zuse Institute Berlin (ZIB)}, pages = {87}, year = {2013}, abstract = {Eines der gr{\"o}ßten Hindernisse beim praktischen Einsatz von Scalaris, einer skalierbaren Implementierung einer verteilten Hashtabelle mit Unterst{\"u}tzung f{\"u}r Transaktionen, ist das Fehlen eines Verfahrens zur Aufnahme eines konsistenten Zustandes des gesamten Systems. Wir stellen in dieser Arbeit ein einfaches Protokoll vor, dass diese Aufgabe erf{\"u}llt und sich, auf Grund der von uns gew{\"a}hlten Herangehensweise, leicht implementieren l{\"a}sst. Als Ausgangspunkt daf{\"u}r w{\"a}hlen wir aus einer Reihe von „klassischen" Snapshot-Algorithmen ein 1993 von Mattern entworfenes Verfahren, welches auf dem Algorithmus von Lai und Yang basiert, aus. Diese Entscheidung basiert auf einer gr{\"u}ndlichen Analyse der Protokolle unter Ber{\"u}cksichtigung der Architektur der existierenden Software. Im n{\"a}chsten Arbeitsschritt benutzen wir unser vollst{\"a}ndiges Wissen {\"u}ber die Interna des Transaktionssystems von Scalaris und vereinfachen damit das Verfahren hinsichtlich Benutzbarkeit und Implementierungskomplexit{\"a}t, ohne die Anforderungen an den aufgenommenen Zustand aufzuweichen. Statt einer losen Anh{\"a}ufung lokaler Zust{\"a}nde der einzelnen Teilnehmerknoten k{\"o}nnen wir am Ende eine große Schl{\"u}ssel-Wert-Tabelle als Ergebnis erzeugen, die konsistent ist, sich leicht weiterverarbeiten l{\"a}sst und die einem Zustand entspricht, in dem sich das System einmal befunden haben k{\"o}nnte. Nachdem wir das Verfahren dann in Software umgesetzt haben, werten wir die Ergebnisse hinsichtlich des Einflusses auf die Performanz des Gesamtsystems aus und diskutieren m{\"o}gliche Weiterentwicklungen.}, language = {de} } @masterthesis{Hoffmann2009, type = {Bachelor Thesis}, author = {Hoffmann, Marie}, title = {Ein agglomeratives, gossipbasiertes Clustering-Verfahren f{\"u}r verteilte Systeme implementiert in Scalaris}, year = {2009}, language = {de} } @misc{Mattes2019, type = {Master Thesis}, author = {Mattes, Dirk}, title = {Ein System zur deterministischen Wiedergabe von verteilten Algorithmen auf Anwendungsebene}, year = {2019}, language = {de} }