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.

Download full text files

Export metadata

Metadaten
Author:Jan Skrzypczak
Document Type:ZIB-Report
Tag:Consensus; Paxos
Date of first Publication:2017/11/14
Series (Serial Number):ZIB-Report (17-64)
ISSN:1438-0064