A Flexible Consensus Protocol for Distributed Systems

Abstract

This paper presents a new type of Consensus problem named the Consensus (n, m) with alternative plans, where n denotes the total number of processors in the network, m is the number of processors with an initial value, n ≥ 4 and 1 ≤ m ≤ n. Compared to the traditional Consensus problem, the Consensus (n, m) problem with alternative plans has two major features. First, each processor is no longer required to propose an initial value. It can flexibly choose to propose or not propose an initial value. This feature allows the Consensus problem to be flexibly applied in many new real-world applications of the distributed system. Second, the proposed protocol ensures that all correct processors always agree on a good plan from a correct processor and never on a bad plan. Compared to solutions of the traditional Consensus problem, which does not guarantee that all correct processors agree on a good plan, this feature ensures the rationality of the Consensus value. In other words, by solving the Consensus (n, m) problem with alternative plans, the fault tolerance and reliability of distributed systems can be improved.