Message and time efficient consensus protocols for synchronous distributed systems

Xianbing Wang, Yong Meng Teo, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)641-654
Number of pages14
JournalJournal of Parallel and Distributed Computing
Issue number5
Publication statusPublished - 1 May 2008


  • Consensus
  • Early stopping
  • Message efficient
  • Orderly crash failure
  • Synchronous distributed systems

ASJC Scopus subject areas

  • Computer Science Applications
  • Hardware and Architecture
  • Control and Systems Engineering

Cite this