@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} }