Message and time efficient consensus protocols for synchronous distributed systems

For a synchronous distributed system of n processes with up to t potential and f actual crash failures, where (t < n - 1, f ≤ t), the time lower bound for a protocol to achieve consensus is min (t + 1, f + 2) rounds. Currently, most researches in this field focus on the time efficiency of consensus protocols. This paper proposes consensus protocols for synchronous distributed systems that achieve both message and time efficiency. Based on an early stopping consensus protocol for synchronous distributed system with crash failures, we propose a rotating coordinator scheme that significantly reduces message complexity. However, this protocol is not time efficient because it requires min (t + 1, f + 3) rounds to reach consensus. Thus, to achieve both time and message efficiency, we propose another protocol in which (t + 1) coordinators are used to send messages in each round. Furthermore, we show that the proposed consensus protocol with crash failures can be revised to be more message-efficient with orderly crash failures. When a process is able to send more than one message to another in a round, we propose an optimal message efficient early stopping consensus protocol for synchronous distributed systems with orderly crash failures.