Computer Science

Eventual Consensus: Applications to Storage and Blockchain : tract)

Document Type

Conference Paper

Abstract

Consensus is one of the most important primitives in large-scale distributed systems due to its wide applications. Consensus has been studied and applied extensively in diverse areas including control systems, optimization, distributed computing, and emerging areas such as robotics, Blockchain, and Internet-of-Things. However, one common issue in practical systems is the misuse of consensus algorithms that are impossible to achieve in asynchronous systems with failures. We propose an alternative formulation that is achievable in such a scenario and easy to understand compared to other versions of relaxed consensus formulation. Concretely, inspired by the asymptotic (approximate) consensus in control systems and applications in storage systems, we introduce a new consensus problem - Eventual Consensus (or Asymptotic Exact Consensus). Two distinctive features are 'exact agreement' and 'eventual agreement' on the state values of fault-free nodes. Eventual property allows us to solve the problem in asynchronous systems with crash or even Byzantine failures. Exact agreement property makes it useful for applications like storage systems which require replicas (or servers) to reach exactly the same state (eventually). Followed by the definition, we explain how eventual consensus is different from prior problems and how it might reduce the misuse by non-experts and practitioners. We then present simple algorithms to solve eventual consensus in static and dynamic systems. Finally, we provide two applications in distributed storage systems and Blockchain.

Publication Title

2019 57th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2019

Publication Date

2019

First Page

840

Last Page

846

ISBN

9781728131511

DOI

10.1109/ALLERTON.2019.8919675

Keywords

asymptotic consensus, blockchain, consensus, eventual consensus, fault-tolerance, storage

APA Citation

Tseng, L. (2019, September). Eventual Consensus: Applications to Storage and Blockchain. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) (pp. 840-846). IEEE.

Link to Full Text

Share

COinS