Recent results on fault-tolerant consensus in message-passing networks

DOI10.1007/978-3-319-48314-6_7zbMATH Open1482.68049arXiv1608.07923OpenAlexW2517375438MaRDI QIDQ2835019FDOQ2835019

Authors: Lewis Tseng 

Publication date: 1 December 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Abstract: Fault-tolerant consensus has been studied extensively in the literature, because it is one of the most important distributed primitives and has wide applications in practice. This paper surveys important results on fault-tolerant consensus in message-passing networks, and the focus is on results from the past decade. Particularly, we categorize the results into two groups: new problem formulations and practical applications. In the first part, we discuss new ways to define the consensus problem, which includes larger input domains, link fault models, different network models . . . etc, and briefly discuss the important techniques. In the second part, we focus on Crash Fault-Tolerant (CFT) systems that use Paxos or Raft, and Byzantine Fault-Tolerant (BFT) systems. We also discuss Bitcoin, which can be related to solving Byzantine consensus in anonymous systems, and compare Bitcoin with BFT systems and Byzantine consensus.

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

Recommendations

• Fast and simple distributed consensus
• SoK: a consensus taxonomy in the blockchain era
• The blockchain consensus layer and BFT
• Crash-tolerant consensus in directed graph revisited (extended abstract)
• Fault-tolerant consensus with an abstract MAC layer

zbMATH Keywords

consensusfault tolerancecrashBitcoinPaxosByzantine consensusBFTByzantine fault-tolerant systemsmessage-passing networksRaft

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cites Work

• Title not available (Why is that?)
• From binary consensus to multivalued consensus in asynchronous message-passing systems
• Impossibility of distributed consensus with one faulty process
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• The Byzantine generals strike again
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Concurrent programming: algorithms, principles, and foundations.
• Reaching approximate agreement in the presence of faults
• Easy impossibility proofs for distributed consensus problems
• Error-free multi-valued consensus with Byzantine failures
• Bounded cost algorithms for multivalued consensus using binary consensus instances
• Fast Paxos
• Iterative approximate Byzantine consensus in arbitrary directed graphs
• The Bitcoin Backbone Protocol: Analysis and Applications
• Principles of Distributed Systems
• Consensus in networked multi-agent systems with adversaries
• Multidimensional approximate agreement in Byzantine asynchronous systems
• Byzantine vector consensus in complete graphs
• Optimally efficient multi-valued byzantine agreement
• Distributed consensus revisited
• Recent Results on Fault-Tolerant Consensus in Message-Passing Networks
• Low complexity resilient consensus in networked multi-agent systems with adversaries
• Fault-tolerant consensus in directed graphs
• Minimal synchrony for Byzantine consensus
• Asynchronous convex hull consensus in the presence of crash faults
• Partial synchrony based on set timeliness
• Reaching approximate Byzantine consensus with multi-hop communication
• Communication optimal multi-valued asynchronous broadcast protocol
• On k -set consensus problems in asynchronous systems
• Signature-Free Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2) Messages, and Constant Time
• Impossibility Results for Distributed Computing
• Communication optimal multi-valued asynchronous Byzantine agreement with optimal resilience

Cited In (6)

• Message-optimal protocols for fault-tolerant broadcasts/multicasts in distributed systems with crash failures
• A network-failure-tolerant message-passing system for terascale clusters
• A fault-tolerant message passing algorithm and its hardware implementation
• Fast agreement in networks with Byzantine nodes
• Recent Results on Fault-Tolerant Consensus in Message-Passing Networks
• Stellar consensus by instantiation

Uses Software

• ZooKeeper
• etcd
• GitHub
• RethinkDB

This page was built for publication: Recent results on fault-tolerant consensus in message-passing networks

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