HackerPapers

arXiv:1309.5671cs.DC

Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab

Robbert Van Renesse, Nicolas Schiper, Fred B. Schneider

Abstract

Paxos, Viewstamped Replication, and Zab are replication protocols that ensure high-availability in asynchronous environments with crash failures. Various claims have been made about similarities and differences between these protocols. But how does one determine whether two protocols are the same, and if not, how significant the differences are? We propose to address these questions using refinement mappings, where protocols are expressed as succinct specifications that are progressively refined to executable implementations. Doing so enables a principled understanding of the correctness of the different design decisions that went into implementing the various protocols. Additionally, it allowed us to identify key differences that have a significant impact on performance.

arXiv comments
16 pages
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 2 identifiable commenters in 3 comments across 3 threads, from Jul 2014 to Nov 2018.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. A Raft implementation in Haskell 1 comment

    • As a member of a team that has implemented Raft in production (https://fauna.com) and in conversation with others who have, the general consensus is that Raft, Paxos, and even Viewstamped Replication are variants of the same fundamental algorithm. There is an interesting paper…

      evanweaverView on HNParent context

  2. Gryadka is not Paxos, so it's probably wrong 1 comment

    • While we're here, it's also not true that all correct consensus protocols are Paxos. For example, Viewstamped Replication is correct, but a different algorithm (see https://arxiv.org/pdf/1309.5671v3.pdf). There's a number of correct algorithms, and they all smell an awful lot…

      mjbView on HNParent context

  3. Use of Formal Methods at Amazon Web Services (2013) [pdf] 1 comment

    • > 1) How do you model the myriad fault types that could possibly occur in distributed systems? You need to think at the right level of abstraction. Are packet loss and reordering really different faults? Are packet loss to a node and the stop failure of that node different…

      mjbView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.