ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (4): 692-707.doi: 10.7544/issn1000-1239.2019.20170973

Previous Articles     Next Articles

Paxos-like Consensus Algorithms: A Review

Wang Jiang, Zhang Mingxing, Wu Yongwei, Chen Kang, Zheng Weimin   

  1. (Department of Computer Science and Technology, Tsinghua University, Beijing 100084) (Beijing National Research Center for Information Science and Technology, Beijing 100084) (Graduate School at Shenzhen, Tsinghua University, Shenzhen, Guangdong 518055)
  • Online:2019-04-01

Abstract: With the rapid growth of data volume and Web services, the cluster size is getting bigger and bigger in datacenters. The probability of service interruption grows dramatically due to machine and network failures. How to achieve a fault-tolerant distributed system becomes very important. State machine replication is one of the most general methods for building a fault-tolerant system, and distributed consensus problem is one of the most basic and core issues in replicated state machine systems. Paxos and a series of Paxos-like consensus algorithms can effectively solve this problem. In recent years, more and more systems use consensus-related techniques to ensure their reliability and availability, and studies on distributed consensus algorithms are also emerging in an endless stream. These consensus algorithms can be divided into two categories, leader-based consensus algorithms and leaderless consensus algorithms. With the development of network technologies such as remote direct memory access(RDMA) and hardware technologies such as field-programmable gate array(FPGA), some consensus algorithms combining with new network technologies and hardware technologies have appeared, which are used to improve the performance of distributed systems. In this paper, we introduce Paxos series algorithms from the perspective of the development of distributed consensus algorithms, discuss the advantages and disadvantages of the algorithms in different scenarios, and further give a future outlook on the research and application directions.

Key words: distributed consensus, fault tolerance, Paxos, leader-based consensus, leaderless consensus

CLC Number: