Message complexity of hierarchical quorum consensus algorithm

Her Kun Chang; Shyan Ming Yuan

doi:10.1016/0020-0190(94)00012-3

Message complexity of hierarchical quorum consensus algorithm

Her Kun Chang, Shyan Ming Yuan^*

^*Corresponding author for this work

National Yang Ming Chiao Tung University

Research output: Contribution to journal › Journal Article › peer-review

1 Scopus citations

Abstract

The hierarchical quorum consensus (HQC) algorithm, which is a generalization of the standard quorum consensus algorithm for managing replicated data, can reduce the quorum size to N^0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ratio of the message complexity to the quorum size is presented. It is shown that the ratio converges to a constant.

Original language	English
Pages (from-to)	69-73
Number of pages	5
Journal	Information Processing Letters
Volume	50
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(94)00012-3
State	Published - 22 04 1994
Externally published	Yes

Keywords

Analysis of algorithms
Hierarchical quorum consensus
Message complexity
Quorum size
Replicated data

Access to Document

10.1016/0020-0190(94)00012-3

Cite this

@article{f564241a2a1045e79462d938f75730fb,

title = "Message complexity of hierarchical quorum consensus algorithm",

abstract = "The hierarchical quorum consensus (HQC) algorithm, which is a generalization of the standard quorum consensus algorithm for managing replicated data, can reduce the quorum size to N0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ratio of the message complexity to the quorum size is presented. It is shown that the ratio converges to a constant.",

keywords = "Analysis of algorithms, Hierarchical quorum consensus, Message complexity, Quorum size, Replicated data",

author = "Chang, {Her Kun} and Yuan, {Shyan Ming}",

year = "1994",

month = apr,

day = "22",

doi = "10.1016/0020-0190(94)00012-3",

language = "英语",

volume = "50",

pages = "69--73",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Message complexity of hierarchical quorum consensus algorithm

AU - Chang, Her Kun

AU - Yuan, Shyan Ming

PY - 1994/4/22

Y1 - 1994/4/22

N2 - The hierarchical quorum consensus (HQC) algorithm, which is a generalization of the standard quorum consensus algorithm for managing replicated data, can reduce the quorum size to N0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ratio of the message complexity to the quorum size is presented. It is shown that the ratio converges to a constant.

AB - The hierarchical quorum consensus (HQC) algorithm, which is a generalization of the standard quorum consensus algorithm for managing replicated data, can reduce the quorum size to N0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ratio of the message complexity to the quorum size is presented. It is shown that the ratio converges to a constant.

KW - Analysis of algorithms

KW - Hierarchical quorum consensus

KW - Message complexity

KW - Quorum size

KW - Replicated data

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

U2 - 10.1016/0020-0190(94)00012-3

DO - 10.1016/0020-0190(94)00012-3

M3 - 文章

AN - SCOPUS:0028420159

SN - 0020-0190

VL - 50

SP - 69

EP - 73

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Message complexity of hierarchical quorum consensus algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this