Using asynchrony and zero degradation to speed up indulgent consensus protocols

Weigang Wu, Jiannong Cao, Jin Yang, Michel Raynal

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

Existing consensus protocols suffer from slowdowns caused by the failures of processes and the mistakes made by the underlying oracles. In this paper, we propose two novel techniques to circumvent such slowdowns in failure-detector-based consensus protocols. The first technique guarantees the Round-Zero-Degradation (RZD) property (an extension of the Zero-Degradation property) in order to avoid the slowdown caused by a failed coordinator process. The second technique, named "Look-Ahead", helps speed up the execution of the consensus protocol by making use of the messages delivered before their receivers enter the corresponding phases or rounds. The first technique is effective only when the underlying failure detector makes no or few mistakes, while the second technique always works well regardless of the performance of the failure detector. Moreover, Look-Ahead is a general technique and can be applied to consensus protocols based on any kind of oracle. By applying the two proposed techniques, several consensus protocols are developed. The simulation results show that the RZD technique is effective even if the error rate of the failure detector reaches about 15%, while the Look-Ahead technique can always improve the performance in all cases.
Original languageEnglish
Pages (from-to)984-996
Number of pages13
JournalJournal of Parallel and Distributed Computing
Volume68
Issue number7
DOIs
Publication statusPublished - 1 Jul 2008

Keywords

  • Asynchronous system
  • Consensus
  • Distributed algorithm
  • Failure detector
  • Fault tolerance

ASJC Scopus subject areas

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

Cite this