An optimal early stopping uniform consensus protocol in synchronous distributed systems with orderly crash failures

Xianbing Wang, Jiannong Cao

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Most existing consensus protocols for synchronous distributed systems are designed to tolerate crash failures of processes. It has been proved that there is no n-process stopping consensus protocol for synchronous distributed systems that tolerates up to t crash failures, in which all non-faulty processes always decide by the end of round t, where t < n-1 and n is the total number of processes, t is the maximum number of failures that can occur. Furthermore, the well-known lower bound, min (t+1, f+2), has been proved for early stopping synchronous consensus protocols, where f ≤ t, and f is the number of failures that actually occur in the system. In this paper, we propose a consensus protocol for synchronous distributed systems with orderly crash failures [4], which is both time and message efficient than those existing protocols applied in this failure model. The proposed protocol achieves uniform consensus and tolerates up to t failures, in which all non-faulty processes always make decision and stop immediately by the end of f+1 rounds, where t < n, f ≤ t. When there is no failure, the protocol can achieve uniform consensus and stop within one round. We prove that the lower bounds of early stopping protocols for both consensus and uniform consensus in orderly crash failure model are f+1 rounds, which ensure our proposed protocol is optimal.
Original languageEnglish
Title of host publicationProceedings - 23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003
PublisherIEEE
Pages76-81
Number of pages6
ISBN (Electronic)0769519210, 9780769519210
DOIs
Publication statusPublished - 1 Jan 2003
Event23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003 - Providence, United States
Duration: 19 May 200322 May 2003

Conference

Conference23rd International Conference on Distributed Computing Systems Workshops, ICDCSW 2003
Country/TerritoryUnited States
CityProvidence
Period19/05/0322/05/03

Keywords

  • Clocks
  • Computer crashes
  • Distributed computing
  • Internet
  • Mobile computing
  • Protocols

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing

Cite this