A bivalency proof of the lower bound for uniform consensus

Xianbing Wang; Yong Meng Teo; Jiannong Cao

doi:10.1016/j.ipl.2005.08.002

A bivalency proof of the lower bound for uniform consensus

Xianbing Wang, Yong Meng Teo, Jiannong Cao

Research output: Journal article publication › Journal article › Academic research › peer-review

10 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 language	English
Pages (from-to)	167-174
Number of pages	8
Journal	Information Processing Letters
Volume	96
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2005.08.002
Publication status	Published - 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

More information

10.1016/j.ipl.2005.08.002

Cite this

@article{849f408e308c4261bb90552f6b83cc35,

title = "A bivalency proof of the lower bound for uniform consensus",

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.",

keywords = "Bivalency argument, Distributed computing, Synchronous distributed systems, Uniform consensus",

author = "Xianbing Wang and Teo, {Yong Meng} and Jiannong Cao",

year = "2005",

month = dec,

day = "16",

doi = "10.1016/j.ipl.2005.08.002",

language = "English",

volume = "96",

pages = "167--174",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - A bivalency proof of the lower bound for uniform consensus

AU - Wang, Xianbing

AU - Teo, Yong Meng

AU - Cao, Jiannong

PY - 2005/12/16

Y1 - 2005/12/16

N2 - 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.

AB - 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.

KW - Bivalency argument

KW - Distributed computing

KW - Synchronous distributed systems

KW - Uniform consensus

UR - http://www.scopus.com/inward/record.url?scp=27144557254&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2005.08.002

DO - 10.1016/j.ipl.2005.08.002

M3 - Journal article

SN - 0020-0190

VL - 96

SP - 167

EP - 174

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

A bivalency proof of the lower bound for uniform consensus

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this