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 -