Weakening Paxos Consensus Sequences for Commutative Commands
Please always quote using this URN: urn:nbn:de:0297-zib-65741
- 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.
Author: | Jan SkrzypczakORCiD |
---|---|
Document Type: | ZIB-Report |
Tag: | Consensus; Paxos |
Date of first Publication: | 2017/11/14 |
Series (Serial Number): | ZIB-Report (17-64) |
ISSN: | 1438-0064 |