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