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