TY - THES A1 - Kruber, Nico T1 - DHT Load Balancing with Estimated Global Information N2 - 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%. KW - Peer-to-Peer KW - Verteilte Hashtabelle (DHT) KW - Lastverteilung KW - Gossiping KW - Peer-to-Peer KW - Distributed Hash Table (DHT) KW - Load Balancing KW - Gossiping Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11514 ER - TY - GEN A1 - Moser, Monika A1 - Haridi, Seif A1 - Shafaat, Tallat A1 - Schütt, Thorsten A1 - Högqvist, Mikael A1 - Reinefeld, Alexander T1 - Transactional DHT Algorithms N2 - 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. T3 - ZIB-Report - 09-34 KW - Distributed System KW - DHT KW - Paxos KW - Algorithms KW - Storage Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11532 SN - 1438-0064 ER - TY - GEN A1 - Schintke, Florian A1 - Reinefeld, Alexander A1 - Haridi, Seif A1 - Schütt, Thorsten T1 - Enhanced Paxos Commit for Transactions on DHTs N2 - 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. T3 - ZIB-Report - 09-28 KW - Paxos KW - Transaktionen KW - DHT KW - strenge Konsistenz KW - Paxos KW - transactions KW - DHT KW - strong consistency Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11448 SN - 1438-0064 ER - TY - THES A1 - Prollius, Christian von T1 - Ein Peer-to-Peer System mit Bereichsabfragen in PlanetLab T1 - A Peer-to-Peer System with Range Queries in PlanetLab N2 - 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ü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ünschten Daten hat. Client-Server Architekturen, wie zum Beispiel Napster, haben sich als ungünstig herausgestellt. Wenige Server, die eine große Anzahl an Clients bedienen müssen, sind einerseits sehr anfällig gegenüber Angriffen und Ausfällen (Single Point of Failure)und kommen auch nicht mit der ständig wachsenden Anzahl an Nutzern zurecht. Verteilte Hashtabellen (DHT) bieten hier einen guten Lösungsansatz, der mit einer großen Anzahl an Nutzern skaliert und ausfallsicher ist. Andere dezentrale Lösungen, wie zum Beispiel das P2P Netzwerk Gnutella haben zwar das Problem des Single Point of Failure gelö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ärt, dass eine Suchanfrage bei Standardeinstellungen in der Clientsoftware einen Netzwerkverkehr von 17MB erzeugt. Deswegen wird zusätzlich eine Lösung benötigt, die Keys und Values geordnet verteilt, damit sie gezielt gesucht werden können. Aus diesem Grund beschäftigt sich die folgende Arbeit mit einer völlig dezentralen Architektur, die außerdem eine sinnvolle Platzierung der Keys vornimmt. Die dezentrale Architektur hat den Vorteil, dass die Endgeräte den Hauptteil des Dienstes selbst erbringen und damit jeder zusätzliche Teilnehmer seine eigenen Ressourcen beisteuert. Diese Arbeit präsentiert Chord#, eine dezentrale, skalierbare und selbstorganisierende verteilte Hashtabelle. Chord# wurde ausgewählt, da in dieser Arbeit auch Wert auf Bereichsabfragen gelegt wurde. Diese sind zum Beispiel bei dem Chord Algorithmus nicht möglich, da dieser eine Hashfunktion für die Keys verwendet und somit die Daten zwar gleichmäß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önnen durch den Verzicht auf die Hashfunktion Bereichsabfragen ermöglicht werden. Dafür wird der Chord# Algorithmus in Java implementiert (ca. 1500 Zeilen Code) und in dem Forschungsnetz PlanetLab ausführlich auf Laufzeiten, Instandhaltungskosten und Skalierung getestet. N2 - Recent developments show that peer-to-peer (p2p) applications, such as Skype or Bittorrent have become increasingly important in the internet. Over the last years there has been a rapid growth of both users and data in such networks. However, the actual file transfer between two peers is not really an issue anymore. The same holds true for data storage, since the new hardware grants users enough space to store their data. The real problem is finding the peers that possess the desired data. Client-server architectures like Napster have proven to be ineffective addressing that problem. One or few servers being responsible for many peers are vulnerable to attacks or failures (single point of failure). Additionally, they are unable to cope with the rapidly growing number of peers. Distributed hashtables (DHT) are a good approach to solve these problems, since they scale nicely with large numbers of peers and provide a high tolerance for errors. Other decentralized solutions like the p2p network Gnutella solved the problem of Single Point of Failure but show considerable disadvantages when searching for keys. The peers in Gnutella use a broadcast (sending the message to all peers they know)resulting in massive traffic. According to "Why Gnutella Can't Scale. No, Really.", each search using standard client settings yields 17MB traffc. This calls for a different solution, distributing keys and values to peers quickly and efficiently so they can be found fast. For that reason this thesis focuses on a fully distributed architecture using organized key placement. One major advantage of distributed architecture is the fact, that the peers do most of the work themselves. This way, new peers joining the network add resources to it. This thesis presents Chord#, a scalable, self-organizing and completely decentralized DHT. It has been chosen due to its capability to allow range queries. The regular Chord algorithm does not support range queries, because of the hashfunction it uses to evenly distribute the keys among the peers. This results in similar or logical coherent keys most likely not being close together in the network. This thesis shows Chord# achieving same results as Chord - regarding performance costs - without the hashfunction. In dropping the hashfunction this algorithm allows the use of range queries. The Chord# algorithm is implemented in Java (about 1500 lines of code) and thoroughly tested in the research network PlanetLab. The results are evaluated regarding performance, maintenance and scalability. KW - Peer-to-Peer KW - Bereichsabfragen KW - peer-to-peer KW - range queries Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11492 ER - TY - THES A1 - Plantikow, Stefan T1 - Transaktionen für verteilte Wikis auf strukturierten Overlay Netzwerken T1 - Transactions for Distributed Wikis on Structured Overlay Networks N2 - Die Diplomarbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewä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äufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen. N2 - The diploma thesis presents a transaction processing scheme for structured overlay networks and uses it to develop a distributed Wiki application based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. Such failures are masked by providing high availability of nodes. This in turn is achieved by constructing the overlay from replicated state machines (cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. The pseudocode of the relevant Wiki functions is presented and the different concurrency control techniques are evaluated in terms of message complexity. KW - Verteilte Transaktionen KW - Content Management Systeme KW - Strukturierte Overlay-Netzwerke KW - Konsistenz KW - Nebenläufigkeitskontrolle KW - distributed transactions KW - content management systems KW - structured overlay networks KW - consistency KW - concurrency control Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10176 ER - TY - THES A1 - Müller, Magnus T1 - Flexible Routing Tables in a Distributed Key-Value Store N2 - 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. KW - FRT KW - FRT-Chord KW - GFRT-Chord KW - Routing KW - DHT KW - Scalaris Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42742 ER - TY - JOUR A1 - Kruber, Nico A1 - Högqvist, Mikael A1 - Schütt, Thorsten T1 - The Benefits of Estimated Global Information in DHT Load Balancing JF - Cluster Computing and the Grid, IEEE International Symposium on Y1 - 2011 U6 - https://doi.org/10.1109/CCGrid.2011.11 VL - 0 SP - 382 EP - 391 PB - IEEE Computer Society CY - Los Alamitos, CA, USA ER - TY - THES A1 - Högqvist, Mikael T1 - Consistent Key-Based Routing in Decentralized and Reconfigurable Data Services Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:11-100206145 UR - http://edoc.hu-berlin.de/docviews/abstract.php?id=39763 ER - TY - JOUR A1 - Schintke, Florian T1 - XtreemFS & Scalaris JF - Science & Technology Y1 - 2013 IS - 6 SP - 54 EP - 55 PB - Pan European Networks ER - TY - THES A1 - Borgers, Philipp T1 - Erweiterung eines verteilten Key-Value-Stores (Riak) um einen räumlichen Index Y1 - 2012 ER - TY - THES A1 - Fischer, Jens T1 - Evaluating the Scalability of Scalaris Y1 - 2016 ER - TY - THES A1 - Mattes, Dirk T1 - Ein System zur deterministischen Wiedergabe von verteilten Algorithmen auf Anwendungsebene Y1 - 2019 ER - TY - THES A1 - Kruber, Nico T1 - Approximate Distributed Set Reconciliation with Defined Accuracy Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:11-110-18452/22105-6 UR - https://doi.org/10.18452/21294 ER - TY - CHAP A1 - Schintke, Florian A1 - Reinefeld, Alexander A1 - Haridi, Seif A1 - Schütt, Thorsten T1 - Enhanced Paxos Commit for Transactions on DHTs T2 - CCGRID Y1 - 2010 U6 - https://doi.org/10.1109/CCGRID.2010.41 SP - 448 EP - 454 PB - IEEE ER - TY - THES A1 - Schintke, Florian T1 - Management verteilter Daten in Grid- und Peer-to-Peer-Systemen Y1 - 2010 UR - http://www.dr.hut-verlag.de/978-3-86853-358-3.html ER - TY - CHAP A1 - Högqvist, Mikael A1 - Kruber, Nico ED - Spyropoulos, Thrasyvoulos ED - Hummel, Karin T1 - Passive/Active Load Balancing with Informed Node Placement in DHTs T2 - IWSOS Y1 - 2009 U6 - https://doi.org/10.1007/978-3-642-10865-5_9 VL - 5918 SP - 101 EP - 112 PB - Springer ER - TY - CHAP A1 - Schütt, Thorsten A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Hennig, C. T1 - Self-Adaptation in Large-Scale Systems: A Study on Structured Overlays Across Multiple Datacenters T2 - Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO) Y1 - 2009 U6 - https://doi.org/10.1109/SASOW.2010.65 ER - TY - CHAP A1 - Högqvist, Mikael A1 - Plantikow, Stefan T1 - Towards Explicit Data Placement in Scalable Key/Value Stores T2 - Architectures and Languages for Self-Managing Distributed Systems (SelfMan@SASO) Y1 - 2009 ER - TY - CHAP A1 - Schütt, Thorsten A1 - Moser, Monika A1 - Plantikow, Stefan A1 - Schintke, Florian A1 - Reinefeld, Alexander T1 - A Transactional Scalable Distributed Data Store T2 - 1st IEEE International Scalable Computing Challenge, co-located with CCGrid’08 Y1 - 2008 ER - TY - CHAP A1 - Shafaat, Tallat A1 - Moser, Monika A1 - Ghodsi, Ali A1 - Schütt, Thorsten A1 - Haridi, Seif A1 - Reinefeld, Alexander T1 - Key-Based Consistency and Availability in Structured Overlay Networks T2 - International ICST Conference on Scalable Information Systems Y1 - 2008 ER - TY - THES A1 - Schütt, Thorsten T1 - Range queries in distributed hash tables Y1 - 2010 UR - http://www.dr.hut-verlag.de/978-3-86853-370-5.html ER - TY - CHAP A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten A1 - Haridi, Seif ED - Tselentis, G. ED - Domingue, J. ED - Galis, A. ED - Gavras, A. ED - Hausheer, D. ED - Krco, S. ED - Lotz, V. ED - Zahariadis, T. T1 - A Scalable, Transactional Data Store for Future Internet Services T2 - Towards the Future Internet - A European Research Perspective Y1 - 2009 U6 - https://doi.org/10.3233/978-1-60750-007-0-148 SP - 148 EP - 159 PB - IOS Press ER - TY - CHAP A1 - Schütt, Thorsten A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Hoffmann, Marie T1 - Gossip-based Topology Inference for Efficient Overlay Mapping on Data Centers T2 - Peer-to-Peer Computing Y1 - 2009 U6 - https://doi.org/10.1109/P2P.2009.5284553 SP - 147 EP - 150 ER - TY - CHAP A1 - Plantikow, Stefan A1 - Reinefeld, Alexander A1 - Schintke, Florian ED - Danelutto, Marco ED - Fragopoulou, Paraskevi ED - Getov, Vladimir T1 - Transactions and Concurrency Control for Peer-to-Peer-Wikis: An Evaluation T2 - Making Grids Work Y1 - 2008 U6 - https://doi.org/10.1007/978-0-387-78448-9_27 SP - 337 EP - 349 ER - TY - CHAP A1 - Högqvist, Mikael A1 - Haridi, Seif A1 - Kruber, Nico A1 - Reinefeld, Alexander A1 - Schütt, Thorsten T1 - Using Global Information for Load Balancing in DHTs T2 - Workshop on Decentralized Self Management for Grids, P2P, and User Communities Y1 - 2008 ER - TY - CHAP A1 - Schütt, Thorsten A1 - Schintke, Florian A1 - Reinefeld, Alexander ED - Kermarrec, Anne-Marie T1 - A Structured Overlay for Multi-dimensional Range Queries T2 - Euro-Par Conference Y1 - 2007 UR - http://dx.doi.org/10.1007/978-3-540-74466-5_54 U6 - https://doi.org/10.1007/978-3-540-74466-5_54 VL - 4641 SP - 503 EP - 513 PB - Springer ER - TY - CHAP A1 - Moser, Monika A1 - Haridi, Seif T1 - Atomic Commitment in Transactional DHTs T2 - Proceedings of the CoreGRID Symposium Y1 - 2007 CY - Rennes, France ER - TY - GEN A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - Device and method for retrieving / storing electronic data in a system with a plurality of data processing units Y1 - 2007 PB - United States Patent Application Publication No. US 2007/0165619 A1 ER - TY - CHAP A1 - Plantikow, Stefan A1 - Reinefeld, Alexander A1 - Schintke, Florian T1 - Distributed Wikis on Structured Overlays T2 - CoreGrid Workshop on Grid Programming Models, Grid and P2P System Architecture, Grid Systems, Tools and Environments Y1 - 2007 ER - TY - CHAP A1 - Plantikow, Stefan A1 - Reinefeld, Alexander A1 - Schintke, Florian ED - Clemm, Alexander ED - Granville, Lisandro ED - Stadler, Rolf T1 - Transactions for Distributed Wikis on Structured Overlays T2 - DSOM Y1 - 2007 U6 - https://doi.org/10.1007/978-3-540-75694-1_25 VL - 4785 SP - 256 EP - 267 PB - Springer CY - Silicon Valley, CA, USA ER - TY - GEN A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - Vorrichtung und Verfahren zum Abrufen / Speichern von elektronischen Daten in einem System mit mehreren Datenverarbeitungseinheiten Y1 - 2007 PB - Europäisches Patent EP 1 744 257 A1 ER - TY - GEN A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - Vorrichtung und Verfahren zum Speichern / Abrufen von Objekten mit mehrdimensional adressierten, elektronischen Daten Y1 - 2007 PB - Europäische Patentanmeldung Nr. 06012030.0 vom 12.06.2006, Patent Nr: 1868114 ER - TY - CHAP A1 - Shafaat, Tallat A1 - Moser, Monika A1 - Ghodsi, Ali A1 - Schütt, Thorsten A1 - Reinefeld, Alexander T1 - On Consistency of Data in Structured Overlay Networks T2 - Coregrid Integration Workshop Y1 - 2008 ER - TY - JOUR A1 - Schütt, Thorsten A1 - Schintke, Florian A1 - Reinefeld, Alexander T1 - Range Queries on structured overlay networks JF - Computer Communications Y1 - 2008 U6 - https://doi.org/10.1016/j.comcom.2007.08.027 VL - 31 IS - 2 SP - 280 EP - 291 PB - Elsevier ER - TY - CHAP A1 - Schütt, Thorsten A1 - Schintke, Florian A1 - Reinefeld, Alexander T1 - Scalaris: Reliable Transactional P2P Key/Value T2 - ERLANG '08: Proceedings of the 7th ACM SIGPLAN workshop on ERLANG Y1 - 2008 U6 - https://doi.org/10.1145/1411273.1411280 SP - 41 EP - 47 ER - TY - CHAP A1 - Roy, P. A1 - Haridi, Seif A1 - Reinefeld, Alexander A1 - Stefani, J. B. A1 - Yap, R. A1 - Coupaye, T. T1 - Self Management for Large-Scale Distributed Systems T2 - Formal Methods for Components and Objects 2007 (FMCO 2007) Y1 - 2008 PB - Springer LNCS ER - TY - CHAP A1 - Schütt, Thorsten A1 - Schintke, Florian A1 - Reinefeld, Alexander T1 - Structured Overlay without Consistent Hashing: Empirical Results T2 - 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 Y1 - 2006 UR - http://doi.ieeecomputersociety.org/10.1109/CCGRID.2006.175 U6 - https://doi.org/10.1109/CCGRID.2006.175 PB - IEEE Computer Society ER - TY - THES A1 - Michels, Maximilian T1 - Request-Based Load Balancing in Distributed Hash Tables Y1 - 2014 ER - TY - THES A1 - Fajerski, Jan T1 - Map Reduce on Distributed Hash Tables Y1 - 2014 ER - TY - JOUR A1 - Högqvist, Mikael A1 - Reinefeld, Alexander T1 - RECODE: Reconfigurable, Consistent and Decentralized Data Services JF - IEEE International Conference on Peer-to-Peer Computing (P2P’13) Y1 - 2013 U6 - https://doi.org/10.1109/P2P.2013.6688705 SP - 1 EP - 10 PB - IEEE ER - TY - CHAP A1 - Kruber, Nico A1 - Schintke, Florian A1 - Berlin, Michael T1 - A Relational Database Schema on the Transactional Key-Value Store Scalaris T2 - Proceedings of 2nd Workshop on Scalable Cloud Data Management Y1 - 2014 U6 - https://doi.org/10.1109/BigData.2014.7004441 ER - TY - THES A1 - Fischer, Jens V. T1 - A Gossiping Framework for Scalaris Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50685 ER - TY - THES A1 - Hoffmann, Marie T1 - Ein agglomeratives, gossipbasiertes Clustering-Verfahren für verteilte Systeme implementiert in Scalaris Y1 - 2009 ER - TY - CHAP A1 - Kruber, Nico A1 - Lange, Maik A1 - Schintke, Florian T1 - Approximate Hash-Based Set Reconciliation for Distributed Replica Repair T2 - 2015 IEEE 34th International Symposium on Reliable Distributed Systems (SRDS) Y1 - 2015 U6 - https://doi.org/10.1109/SRDS.2015.30 SP - 166 EP - 175 PB - IEEE ER - TY - THES A1 - Lange, Maik T1 - Effiziente Reparatur von Repliken in Distributed Hash Tables N2 - Eine distributed hash Table (DHT) stellt eine über multiple Rechner strukturiert verteilte Tabelle von Schlüssel-Wert-Paaren dar. Ein verteiltes System unterliegt zumeist einer Teilnehmerdynamik in Form von ausfallenden oder beitretenden Knoten, wodurch Daten verloren gehen können. Zur Sicherstellung der Verfügbarkeit aller Schlüssel-Wert-Paare ist Redundanz notwendig. Die Einführung einer Redundanzschicht erhöht die Verfügbarkeit der Daten erheblich auf Kosten einer verringerten Leistungsfä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ügbarkeit langfristig zu sichern. Die Aktualisierung ist optional und verbessert die Leselatenz in geografisch weit verteilten Systemen. Die vorgestellte Lösung besteht aus drei Komponenten. Der Set Reconciliation Dienst ermöglicht den effizienten Vergleich zweier Knoten zur Identifikation verlorener und veralteter Kopien. Der Aktualisierungsdienst synchronisiert die verglichenen Knoten durch die Ü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ähigkeit für die Erkennung verlorener und veralteter Kopien evaluiert werden soll. Ausgewählt wurden der Bloom Filter, der Merkle-Tree sowie deren Kombination der Approximate Reconciliation Tree. Die Evaluation zeigte, dass der Merkle-Tree die höchste Genauigkeit besitzt und spätestens nach einer initiierten Synchronisation eines jeden Knotens zur vollständigen Synchronität in der DHT führt. Der Bloom Filter besitzt bei der Erkennung verlorener Repliken nur die halbe Genauigkeit gegenüber veralteten Repliken, wodurch die Konvergenzgeschwindigkeit dementsprechend geringer ist gegenüber dem Merkle-Tree. Dafür sind die Übertragungskosten des Bloom Filter um bis zu 80% geringer als beim Merkle-Tree und weisen kaum nennenswerte Spitzen auf. Die Übertragungskosten des Merkle-Tree sind abhängig von der Anzahl der Differenzen, sodass bei einer Differenz von Null nur eine Signatur mit weniger als einem kByte übertragen werden muss. Ist die Differenz größer, steigen die Kosten je nach Bucket-Größ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 ähnlichen Konfigurationen bieten keinen Vorteil, wohingegen die Merkle-Tree ähnlichen nur zwei Mitteilungsrunden benötigen bei einer leichten Genauigkeitsverringerung gegenüber dem Merkle-Tree. Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42275 ER - TY - THES A1 - Keidel, Stefan T1 - Snapshots in Scalaris N2 - Eines der größten Hindernisse beim praktischen Einsatz von Scalaris, einer skalierbaren Implementierung einer verteilten Hashtabelle mit Unterstützung fü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üllt und sich, auf Grund der von uns gewählten Herangehensweise, leicht implementieren lässt. Als Ausgangspunkt dafür wä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ündlichen Analyse der Protokolle unter Berücksichtigung der Architektur der existierenden Software. Im nächsten Arbeitsschritt benutzen wir unser vollständiges Wissen über die Interna des Transaktionssystems von Scalaris und vereinfachen damit das Verfahren hinsichtlich Benutzbarkeit und Implementierungskomplexität, ohne die Anforderungen an den aufgenommenen Zustand aufzuweichen. Statt einer losen Anhäufung lokaler Zustände der einzelnen Teilnehmerknoten können wir am Ende eine große Schlüssel-Wert-Tabelle als Ergebnis erzeugen, die konsistent ist, sich leicht weiterverarbeiten lässt und die einem Zustand entspricht, in dem sich das System einmal befunden haben kö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ögliche Weiterentwicklungen. KW - scalaris KW - dht KW - algorithm Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42282 ER - TY - THES A1 - Hoffmann, Marie T1 - Approximate Algorithms for Distributed Systems N2 - 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. KW - peer-to-peer, machine learning, approximate, clustering, quantile, linear regression Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42370 ER - TY - GEN A1 - Skrzypczak, Jan T1 - Weakening Paxos Consensus Sequences for Commutative Commands N2 - 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. T3 - ZIB-Report - 17-64 KW - Consensus KW - Paxos Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65741 SN - 1438-0064 ER - TY - THES A1 - Skrzypczak, Jan T1 - Weakening Paxos Consensus Sequences for Commutative Commands N2 - 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. KW - Paxos KW - Consensus Y1 - 2017 ER - TY - GEN A1 - Plantikow, Stefan T1 - Transaktionen für verteilte Wikis auf strukturierten Overlay-Netzwerken T1 - Transactions for Distributed Wikis on Structured Overlay Networks N2 - Die Arbeit präsentiert ein Transaktionsverfahren für strukturierte Overlay-Netzwerke, das an die Erfordernisse verteilter Informationssysteme mit relationalem Datenmodell angepasst ist. Insbesondere wird der Einsatz von Transaktionen für verteilte Wikis betrachtet, die moderne Funktionalitäten, wie Metadaten und zusätzliche Indexe für die Navigation, unterstützen. Konsistenz und Dauerhaftigkeit der gespeicherten Daten erfordert die Behandlung von Knotenausfällen. Die Arbeit schlägt dafür das Zellenmodell vor: Das Overlay wird aus replizierten Zustandsmaschinen gebildet, um Verfügbarkeit zu gewä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äufigkeitskontrollverfahren geboten, die die Minimierung von Latenzeffekten und die schnelle Ausführung von Nur-Lese-Transaktionen ermöglichen. Für die Beispielanwendung Wiki wird der erforderliche Pseudocode angegeben und die verschiedenen Nebenläufigkeitskontrollverfahren hinsichtlich ihrer Nachrichtenkomplexität verglichen. N2 - The report presents a transaction processing scheme for structured overlay networks and uses it to develop a distributed Wiki application based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. Such failures are masked by providing high availability of nodes. This in turn is achieved by constructing the overlay from replicated state machines (cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. The pseudocode of the relevant Wiki functions is presented and the different concurrency control techniques are evaluated in terms of message complexit T3 - ZIB-Report - 07-43 KW - Verteilte Transaktionen KW - Strukturierte Overlay-Netzwerke KW - Peer-to-Peer KW - Wikis KW - Nebenläufigkeitskontrolle KW - distributed transactions KW - structured overlay networks KW - peer-to-peer KW - wikis KW - concurrency control Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10466 SN - 1438-0064 ER - TY - GEN A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - P2P Routing of Range Queries in Skewed Multidimensional Data Sets N2 - 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. T3 - ZIB-Report - 07-23 KW - structured overlays KW - range queries KW - routing KW - multidimensional data sets Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9671 SN - 1438-0064 ER -