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