Separating conflict-recovery from failure-recovery in distributed consensus

Distributed databases provide fault tolerance while allowing multiple clients to concurrently submit requests and have those requests executed as if they are performed using a single thread on a single machine. This makes them vital components for a variety of distributed systems, from banking transactions to managing cluster configurations. At the core of these distributed databases is their consensus protocol which must order concurrently submitted requests and ensure that the system can mask or recover from failures. Current state-of-the-art consensus protocols re-use their failure-recovery mechanism to resolve ordering conflicts. The thesis of this dissertation is that it is feasible to separate the mechanisms for conflict-recovery and failure-recovery, and that doing so is effective in allowing each to be optimised separately. To support this thesis we first categorise existing conflict-recovery mechanisms and introduce Multi-Shot-FastPaxos which provides a uniform interface to express, and in some cases further optimise, conflict-recovery mechanisms separately from failure-recovery mechanisms. We also propose a new failure masking approach that reduces the overhead of masking coordinator failures and evaluate existing mechanisms for recovery from coordinator failure, allowing us to propose an optimised recovery procedure for etcd. Finally we present a case study designing a new protocol, Unanimous 2 Phase Commit, which from an initial basic implementation is optimised to equal or exceed the steady-state performance of the current state-of-the-art on all workloads, with an optimised recovery procedure.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2025

Author dc:creator

• Jensen, Christopher

Advisors dc:contributor.advisor

• Mortier, Richard
• Howard, Heidi

• Consensus
• Distributed Systems
• Paxos
• FastPaxos
• Failure
• Benchmark

Licence

• https://www.repository.cam.ac.uk/bitstreams/1349cc66-553f-42d5-af1a-21a7a6c3e190/download
• https://creativecommons.org/licenses/by-nc-sa/4.0/

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.119774

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/386642