A bivalency proof of the lower bound for uniform consensus

Xianbing Wang, Yong Meng Teo, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f+2)-rounds where 0≤f≤t-2.
Original languageEnglish
Pages (from-to)167-174
Number of pages8
JournalInformation Processing Letters
Volume96
Issue number5
DOIs
Publication statusPublished - 16 Dec 2005

Keywords

  • Bivalency argument
  • Distributed computing
  • Synchronous distributed systems
  • Uniform consensus

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this