@misc{Kruber2009, type = {Master Thesis}, author = {Kruber, Nico}, title = {DHT Load Balancing with Estimated Global Information}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11514}, school = {Zuse Institute Berlin (ZIB)}, year = {2009}, abstract = {One of the biggest impacts on the performance of a Distributed Hash Table (DHT), once established, is its ability to balance load among its nodes. DHTs supporting range queries for example suffer from a potentially huge skew in the distribution of their items since techniques such as consistent hashing can not be applied. Thus explicit load balancing schemes need to be deployed. Several such schemes have been developed and are part of recent research, most of them using only information locally available in order to scale to arbitrary systems. Gossiping techniques however allow the retrieval of fairly good estimates of global information with low overhead. Such information can then be added to existing load balancing algorithms that can use the additional knowledge to improve their performance. Within this thesis several schemes are developed that use global information like the average load and the standard deviation of the load among the nodes to primarily reduce the number of items an algorithm moves to achieve a certain balance. Two novel load balancing algorithms have then been equipped with implementations of those schemes and have been simulated on several scenarios. Most of these variants show better balance results and move far less items than the algorithms they are based on. The best of the developed algorithms achieves a 15-30\% better balance and moves only about 50-70\% of the number of items its underlying algorithm moves. This variation is also very robust to erroneous estimates and scales linearly with the system size and system load. Further experiments with self-tuning algorithms that set an algorithm's parameter according to the system's state show that even more improvements can be gained if additionally applied. Such a variant based on the algorithm described by Karger and Ruhl shows the same balance improvements of 15-30\% as the variant above but reduces the number of item movements further to 40-65\%.}, language = {en} } @misc{MoserHaridiShafaatetal.2009, author = {Moser, Monika and Haridi, Seif and Shafaat, Tallat and Sch{\"u}tt, Thorsten and H{\"o}gqvist, Mikael and Reinefeld, Alexander}, title = {Transactional DHT Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11532}, number = {09-34}, year = {2009}, abstract = {We present a framework for transactional data access on data stored in a DHT. It allows to atomically read and write items and to run distributed transactions consisting of a sequence of read and write operations on the items. Items are symmetrically replicated in order to achieve durability of data stored in the SON. To provide availability of items despite the unavailability of some replicas, operations on items are quorum-based. They make progress as long as a majority of replicas can be accessed. Our framework processes transactions optimistically with an atomic commit protocol that is based on Paxos atomic commit. We present algorithms for the whole framework with an event based notation. Additionally we discuss the problem of lookup inconsistencies and its implications on the one-copy serializability property of the transaction processing in our framework.}, language = {en} } @misc{SchintkeReinefeldHaridietal.2009, author = {Schintke, Florian and Reinefeld, Alexander and Haridi, Seif and Sch{\"u}tt, Thorsten}, title = {Enhanced Paxos Commit for Transactions on DHTs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11448}, number = {09-28}, year = {2009}, abstract = {Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.}, language = {en} } @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{Mueller2013, type = {Master Thesis}, author = {M{\"u}ller, Magnus}, title = {Flexible Routing Tables in a Distributed Key-Value Store}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42742}, school = {Zuse Institute Berlin (ZIB)}, pages = {118}, year = {2013}, abstract = {We present our implementation of Flexible Routing Tables (FRT) in the distributed key-value store Scalaris. Classic routing table generators like Chord structure routing tables by considering node identifiers only. Secondary requirements such as latency properties are considered after the general structure, eliminating potential performance gains. FRT aims to allow multiple requirements when creating routing tables. The concept is based on lazy routing table entries learning and filtering entries when a routing table is full. Entries are filtered such that the resulting table is best among all other possible tables where one node was filtered. FRT uses a total order to define which of the possible routing tables is best. We implemented two instances of FRT, namely FRT-Chord and grouped FRT-Chord (GFRT-Chord). We compare our implementation with the existing implementation of Chord in Scalaris and evaluate the advantages and disadvantages of more flexible routing schemes.}, language = {en} } @article{KruberHoegqvistSchuett2011, author = {Kruber, Nico and H{\"o}gqvist, Mikael and Sch{\"u}tt, Thorsten}, title = {The Benefits of Estimated Global Information in DHT Load Balancing}, volume = {0}, journal = {Cluster Computing and the Grid, IEEE International Symposium on}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, doi = {10.1109/CCGrid.2011.11}, pages = {382 -- 391}, year = {2011}, language = {en} } @phdthesis{Hoegqvist2012, author = {H{\"o}gqvist, Mikael}, title = {Consistent Key-Based Routing in Decentralized and Reconfigurable Data Services}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:11-100206145}, year = {2012}, language = {en} } @article{Schintke2013, author = {Schintke, Florian}, title = {XtreemFS \& Scalaris}, journal = {Science \& Technology}, number = {6}, publisher = {Pan European Networks}, pages = {54 -- 55}, year = {2013}, language = {en} } @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{Fischer2016, type = {Master Thesis}, author = {Fischer, Jens}, title = {Evaluating the Scalability of Scalaris}, year = {2016}, language = {en} } @misc{Mattes2019, type = {Master Thesis}, author = {Mattes, Dirk}, title = {Ein System zur deterministischen Wiedergabe von verteilten Algorithmen auf Anwendungsebene}, year = {2019}, language = {de} } @phdthesis{Kruber2020, author = {Kruber, Nico}, title = {Approximate Distributed Set Reconciliation with Defined Accuracy}, doi = {10.18452/21294}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:11-110-18452/22105-6}, year = {2020}, language = {en} } @inproceedings{SchintkeReinefeldHaridietal.2010, author = {Schintke, Florian and Reinefeld, Alexander and Haridi, Seif and Sch{\"u}tt, Thorsten}, title = {Enhanced Paxos Commit for Transactions on DHTs}, booktitle = {CCGRID}, publisher = {IEEE}, doi = {10.1109/CCGRID.2010.41}, pages = {448 -- 454}, year = {2010}, language = {en} } @phdthesis{Schintke2010, author = {Schintke, Florian}, title = {Management verteilter Daten in Grid- und Peer-to-Peer-Systemen}, year = {2010}, language = {en} } @inproceedings{HoegqvistKruber2009, author = {H{\"o}gqvist, Mikael and Kruber, Nico}, title = {Passive/Active Load Balancing with Informed Node Placement in DHTs}, volume = {5918}, booktitle = {IWSOS}, editor = {Spyropoulos, Thrasyvoulos and Hummel, Karin}, publisher = {Springer}, doi = {10.1007/978-3-642-10865-5_9}, pages = {101 -- 112}, year = {2009}, language = {en} } @inproceedings{SchuettReinefeldSchintkeetal.2009, author = {Sch{\"u}tt, Thorsten and Reinefeld, Alexander and Schintke, Florian and Hennig, C.}, title = {Self-Adaptation in Large-Scale Systems: A Study on Structured Overlays Across Multiple Datacenters}, booktitle = {Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO)}, doi = {10.1109/SASOW.2010.65}, year = {2009}, language = {en} } @inproceedings{HoegqvistPlantikow2009, author = {H{\"o}gqvist, Mikael and Plantikow, Stefan}, title = {Towards Explicit Data Placement in Scalable Key/Value Stores}, booktitle = {Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO)}, year = {2009}, language = {en} } @inproceedings{SchuettMoserPlantikowetal.2008, author = {Sch{\"u}tt, Thorsten and Moser, Monika and Plantikow, Stefan and Schintke, Florian and Reinefeld, Alexander}, title = {A Transactional Scalable Distributed Data Store}, booktitle = {1st IEEE International Scalable Computing Challenge, co-located with CCGrid'08}, year = {2008}, language = {en} } @inproceedings{ShafaatMoserGhodsietal.2008, author = {Shafaat, Tallat and Moser, Monika and Ghodsi, Ali and Sch{\"u}tt, Thorsten and Haridi, Seif and Reinefeld, Alexander}, title = {Key-Based Consistency and Availability in Structured Overlay Networks}, booktitle = {International ICST Conference on Scalable Information Systems}, year = {2008}, language = {en} } @phdthesis{Schuett2010, author = {Sch{\"u}tt, Thorsten}, title = {Range queries in distributed hash tables}, year = {2010}, language = {en} } @incollection{ReinefeldSchintkeSchuettetal.2009, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten and Haridi, Seif}, title = {A Scalable, Transactional Data Store for Future Internet Services}, booktitle = {Towards the Future Internet - A European Research Perspective}, editor = {Tselentis, G. and Domingue, J. and Galis, A. and Gavras, A. and Hausheer, D. and Krco, S. and Lotz, V. and Zahariadis, T.}, publisher = {IOS Press}, doi = {10.3233/978-1-60750-007-0-148}, pages = {148 -- 159}, year = {2009}, language = {en} } @inproceedings{SchuettReinefeldSchintkeetal.2009, author = {Sch{\"u}tt, Thorsten and Reinefeld, Alexander and Schintke, Florian and Hoffmann, Marie}, title = {Gossip-based Topology Inference for Efficient Overlay Mapping on Data Centers}, booktitle = {Peer-to-Peer Computing}, doi = {10.1109/P2P.2009.5284553}, pages = {147 -- 150}, year = {2009}, language = {en} } @inproceedings{PlantikowReinefeldSchintke2008, author = {Plantikow, Stefan and Reinefeld, Alexander and Schintke, Florian}, title = {Transactions and Concurrency Control for Peer-to-Peer-Wikis: An Evaluation}, booktitle = {Making Grids Work}, editor = {Danelutto, Marco and Fragopoulou, Paraskevi and Getov, Vladimir}, doi = {10.1007/978-0-387-78448-9_27}, pages = {337 -- 349}, year = {2008}, language = {en} } @inproceedings{HoegqvistHaridiKruberetal.2008, author = {H{\"o}gqvist, Mikael and Haridi, Seif and Kruber, Nico and Reinefeld, Alexander and Sch{\"u}tt, Thorsten}, title = {Using Global Information for Load Balancing in DHTs}, booktitle = {Workshop on Decentralized Self Management for Grids, P2P, and User Communities}, year = {2008}, language = {en} } @inproceedings{SchuettSchintkeReinefeld2007, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Reinefeld, Alexander}, title = {A Structured Overlay for Multi-dimensional Range Queries}, volume = {4641}, booktitle = {Euro-Par Conference}, editor = {Kermarrec, Anne-Marie}, publisher = {Springer}, doi = {10.1007/978-3-540-74466-5_54}, pages = {503 -- 513}, year = {2007}, language = {en} } @inproceedings{MoserHaridi2007, author = {Moser, Monika and Haridi, Seif}, title = {Atomic Commitment in Transactional DHTs}, booktitle = {Proceedings of the CoreGRID Symposium}, address = {Rennes, France}, year = {2007}, language = {en} } @misc{ReinefeldSchintkeSchuett2007, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Device and method for retrieving / storing electronic data in a system with a plurality of data processing units}, publisher = {United States Patent Application Publication No. US 2007/0165619 A1}, year = {2007}, language = {en} } @inproceedings{PlantikowReinefeldSchintke2007, author = {Plantikow, Stefan and Reinefeld, Alexander and Schintke, Florian}, title = {Distributed Wikis on Structured Overlays}, booktitle = {CoreGrid Workshop on Grid Programming Models, Grid and P2P System Architecture, Grid Systems, Tools and Environments}, year = {2007}, language = {en} } @inproceedings{PlantikowReinefeldSchintke2007, author = {Plantikow, Stefan and Reinefeld, Alexander and Schintke, Florian}, title = {Transactions for Distributed Wikis on Structured Overlays}, volume = {4785}, booktitle = {DSOM}, editor = {Clemm, Alexander and Granville, Lisandro and Stadler, Rolf}, publisher = {Springer}, address = {Silicon Valley, CA, USA}, doi = {10.1007/978-3-540-75694-1_25}, pages = {256 -- 267}, year = {2007}, language = {en} } @misc{ReinefeldSchintkeSchuett2007, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Vorrichtung und Verfahren zum Abrufen / Speichern von elektronischen Daten in einem System mit mehreren Datenverarbeitungseinheiten}, publisher = {Europ{\"a}isches Patent EP 1 744 257 A1}, year = {2007}, language = {en} } @misc{ReinefeldSchintkeSchuett2007, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {Vorrichtung und Verfahren zum Speichern / Abrufen von Objekten mit mehrdimensional adressierten, elektronischen Daten}, publisher = {Europ{\"a}ische Patentanmeldung Nr. 06012030.0 vom 12.06.2006, Patent Nr: 1868114}, year = {2007}, language = {en} } @inproceedings{ShafaatMoserGhodsietal.2008, author = {Shafaat, Tallat and Moser, Monika and Ghodsi, Ali and Sch{\"u}tt, Thorsten and Reinefeld, Alexander}, title = {On Consistency of Data in Structured Overlay Networks}, booktitle = {Coregrid Integration Workshop}, year = {2008}, language = {en} } @article{SchuettSchintkeReinefeld2008, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Reinefeld, Alexander}, title = {Range Queries on structured overlay networks}, volume = {31}, journal = {Computer Communications}, number = {2}, publisher = {Elsevier}, doi = {10.1016/j.comcom.2007.08.027}, pages = {280 -- 291}, year = {2008}, language = {en} } @inproceedings{SchuettSchintkeReinefeld2008, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Reinefeld, Alexander}, title = {Scalaris: Reliable Transactional P2P Key/Value}, booktitle = {ERLANG '08: Proceedings of the 7th ACM SIGPLAN workshop on ERLANG}, doi = {10.1145/1411273.1411280}, pages = {41 -- 47}, year = {2008}, language = {en} } @inproceedings{RoyHaridiReinefeldetal.2008, author = {Roy, P. and Haridi, Seif and Reinefeld, Alexander and Stefani, J. B. and Yap, R. and Coupaye, T.}, title = {Self Management for Large-Scale Distributed Systems}, booktitle = {Formal Methods for Components and Objects 2007 (FMCO 2007)}, publisher = {Springer LNCS}, year = {2008}, language = {en} } @inproceedings{SchuettSchintkeReinefeld2006, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Reinefeld, Alexander}, title = {Structured Overlay without Consistent Hashing: Empirical Results}, booktitle = {Sixth Workshop on Global and Peer-to-Peer Computing (GP2PC'06) at Sixth IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2006), 16-19 May 2006, Singapore}, publisher = {IEEE Computer Society}, doi = {10.1109/CCGRID.2006.175}, pages = {8}, year = {2006}, language = {en} } @misc{Michels2014, type = {Master Thesis}, author = {Michels, Maximilian}, title = {Request-Based Load Balancing in Distributed Hash Tables}, year = {2014}, language = {en} } @misc{Fajerski2014, type = {Master Thesis}, author = {Fajerski, Jan}, title = {Map Reduce on Distributed Hash Tables}, year = {2014}, language = {en} } @article{HoegqvistReinefeld2013, author = {H{\"o}gqvist, Mikael and Reinefeld, Alexander}, title = {RECODE: Reconfigurable, Consistent and Decentralized Data Services}, journal = {IEEE International Conference on Peer-to-Peer Computing (P2P'13)}, publisher = {IEEE}, doi = {10.1109/P2P.2013.6688705}, pages = {1 -- 10}, year = {2013}, language = {en} } @inproceedings{KruberSchintkeBerlin2014, author = {Kruber, Nico and Schintke, Florian and Berlin, Michael}, title = {A Relational Database Schema on the Transactional Key-Value Store Scalaris}, booktitle = {Proceedings of 2nd Workshop on Scalable Cloud Data Management}, doi = {10.1109/BigData.2014.7004441}, year = {2014}, language = {en} } @masterthesis{Fischer2014, type = {Bachelor Thesis}, author = {Fischer, Jens V.}, title = {A Gossiping Framework for Scalaris}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-50685}, year = {2014}, language = {en} } @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} } @inproceedings{KruberLangeSchintke2015, author = {Kruber, Nico and Lange, Maik and Schintke, Florian}, title = {Approximate Hash-Based Set Reconciliation for Distributed Replica Repair}, booktitle = {2015 IEEE 34th International Symposium on Reliable Distributed Systems (SRDS)}, publisher = {IEEE}, doi = {10.1109/SRDS.2015.30}, pages = {166 -- 175}, year = {2015}, language = {en} } @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} } @misc{Hoffmann2013, type = {Master Thesis}, author = {Hoffmann, Marie}, title = {Approximate Algorithms for Distributed Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42370}, school = {Zuse Institute Berlin (ZIB)}, pages = {75}, year = {2013}, abstract = {Peer-to-peer (P2P) systems form a special class of distributed systems. Typically, nodes in a P2P system are flat and share the same responsabilities. In this thesis we focus on three problems that occur in P2P systems: the storage of data replicates, quantile computation on distributed data streams, and churn rate estimation. Data replication is one of the oldest techniques to maintain stored data in a P2P system and to reply to read requests. Applications, which use data replication are distributed databases. They are part of an abstract overlay network and do not see the underlying network topology. The question is how to place a set of data replicates in a distributed system such that response times and failure probabilities become minimal without a priori knowledge of the topology of the underlying hardware nodes? We show how to utilize an agglomerative clustering procedure to reach this goal. State-of-the-art algorithms for aggregation of distributed data or data streams require at some point synchronization, or merge data aggregates hierarchically, which does not accompany the basic principle of P2P systems. We test whether randomized communication and merging of data aggregates are able to produce the same results. These data aggregates serve for quantile queries. Constituting and maintaining a P2P overlay network requires frequent message passing. It is a goal to minimize the number of maintenance messages since they consume bandwidth which might be missing for other applications. The lower bound of the frequency for mainte- nance messages is highly dependent on the churn rate of peers. We show how to estimate the mean lifetime of peers and to reduce the frequency for maintenance messages without destabilizing the infrastructure of the constituting overlay.}, language = {en} } @misc{Skrzypczak2017, author = {Skrzypczak, Jan}, title = {Weakening Paxos Consensus Sequences for Commutative Commands}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65741}, year = {2017}, abstract = {Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them. This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances. PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.}, language = {en} } @misc{Skrzypczak2017, type = {Master Thesis}, author = {Skrzypczak, Jan}, title = {Weakening Paxos Consensus Sequences for Commutative Commands}, year = {2017}, abstract = {Consensus (agreement on a value) is regarded as a fundamental primitive in the design of fault tolerant distributed systems. A well-known solution to the consensus problem is Paxos. Extensions of the Paxos algorithm make it possible to reach agreement on a sequence of commands which can then be applied on a replicated state. However, concurrently proposed commands can create conflicts that must be resolved by ordering them. This thesis delivers an in-depth description of a Paxos-based algorithm to establish such command sequences, called Paxos Round Based Register (PRBR). In contrast to conventional approaches like Multi-Paxos, PRBR can manage multiple command sequences independently. Furthermore, each sequence is established in-place, which eliminates the need for managing multiple Paxos instances. PRBR is extended as part of this thesis to exploit the commutativity of concurrently proposed commands. As a result, conflict potential can be greatly reduced which increases the number of commands that can be handled by PRBR. This is shown for a number of workloads in an experimental evaluation.}, language = {en} } @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} } @misc{ReinefeldSchintkeSchuett2007, author = {Reinefeld, Alexander and Schintke, Florian and Sch{\"u}tt, Thorsten}, title = {P2P Routing of Range Queries in Skewed Multidimensional Data Sets}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9671}, number = {07-23}, year = {2007}, abstract = {We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of \$\lceil \log N \rceil\$ routing entries.}, language = {en} } @misc{SchuettSchintkeReinefeld2005, author = {Sch{\"u}tt, Thorsten and Schintke, Florian and Reinefeld, Alexander}, title = {Chord\#: Structured Overlay Network for Non-Uniform Load-Distribution}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8736}, number = {05-40}, year = {2005}, abstract = {\newcommand{\chordsharp}{Chord\$^\\#\#\$} Data lookup is a fundamental problem in peer-to-peer systems: Given a key, find the node that stores the associated object. Chord and other P2P algorithms use distributed hash tables (DHTs) to distribute the keys and nodes evenly across a logical ring. Using an efficient routing strategy, DHTs provide a routing performance of \$O (\log N)\$ in networks of \$N\$ nodes. While the routing performance has been shown to be optimal, the uniform key distribution makes it impossible for DHTs to support range queries. For range queries, consecutive keys must be stored on lo gically neighboring nodes. In this paper, we present an enhancement of Chord that eliminates the hash function while keeping the same routing performance. The resulting algorithm, named \chordsharp{}, provides a richer function ality while maintaining the same complexity. In addition to Chord, \chordsharp{} adapts to load imbalance.}, language = {en} }