Legacy of Paxos : Survey of non-byzantine consensus protocols

Show full item record


Title: Legacy of Paxos : Survey of non-byzantine consensus protocols
Author: Tuura, Tommi
Contributor: University of Helsinki, Faculty of Science
Publisher: Helsingin yliopisto
Date: 2020
Language: eng
URI: http://urn.fi/URN:NBN:fi:hulib-202012084713
Thesis level: master's thesis
Discipline: Tietojenkäsittelytiede
Abstract: Computers and computer networks have permeated public and private life across the planet. Billions of people are using seemingly centralized computer systems around the globe. These systems are expected to be always on, always available, and at least in some sense consistent in what kind of status they see users’ data to be in. The only way to build such large-scale systems is by distributing the data and computation to a multiple computers connected by networks. Such distribution will inevitably need to overcome a problem of consensus as all computers and their communication channels are human-made machinery and therefore subject to non-zero chance of hardware and software failures. This thesis is a survey of some well-known consensus protocols that have been proposed or deployed in practice to solve this problem. We cover Paxos, Viewstamped Replication, Zookeeper Atomic Broadcast and Raft and also skim through the general idea of the consensus algorithm proposed by Tushar Deepak Chandra and Sam Toueg in their work on failure detectors which is an important theoretical piece under every other consensus protocol we survey here. We also discuss the real-world usage these protocols have. This survey assumes trusted administrative domain for all protocol participants, therefore byzantine solutions and zero-trust solutions with blockchain are considered out of scope of this work.
Subject: consensus protocols
consensus algorithms
fault tolerance
log replication
state machine replication
viewstamped replication
distributed computing

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show full item record