Generalized Paxos made Byzantine (and less complex)

DOI10.3390/A11090141zbMATH Open1461.68038arXiv1708.07575OpenAlexW2746579076WikidataQ129251690 ScholiaQ129251690MaRDI QIDQ2633262FDOQ2633262

Yanyan Li

Publication date: 8 May 2019

Published in: Algorithms (Search for Journal in Brave)

Abstract: One of the most recent members of the Paxos family of protocols is Generalized Paxos. This variant of Paxos has the characteristic that it departs from the original specification of consensus, allowing for a weaker safety condition where different processes can have a different views on a sequence being agreed upon. However, much like the original Paxos counterpart, Generalized Paxos does not have a simple implementation. Furthermore, with the recent practical adoption of Byzantine fault tolerant protocols, it is timely and important to understand how Generalized Paxos can be implemented in the Byzantine model. In this paper, we make two main contributions. First, we provide a description of Generalized Paxos that is easier to understand, based on a simpler specification and the pseudocode for a solution that can be readily implemented. Second, we extend the protocol to the Byzantine fault model.

Full work available at URL: https://arxiv.org/abs/1708.07575

zbMATH Keywords

consensusByzantine fault tolerancePaxos

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Cites Work

• Causal memory: definitions, implementation, and programming
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• The Byzantine Generals Problem
• Introduction to Reliable and Secure Distributed Programming
• Revisiting the PAXOS algorithm
• Fast Paxos
• A technique for constructing highly available services
• The part-time parliament
• Generalized Paxos Made Byzantine (and Less Complex)
• Byzantizing Paxos by Refinement

Cited In (2)

• Stellar consensus by instantiation
• Consensus on demand

Uses Software

• Dynamo

This page was built for publication: Generalized Paxos made Byzantine (and less complex)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2633262)