MESSAGE COMPLEXITY OF HIERARCHICAL QUORUM CONSENSUS ALGORITHM

Authors
CHANG HK YUAN SM
Citation
Hk. Chang et Sm. Yuan, MESSAGE COMPLEXITY OF HIERARCHICAL QUORUM CONSENSUS ALGORITHM, Information processing letters, 50(2), 1994, pp. 69-73
Citations number
5
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
50
Issue
2
Year of publication
1994
Pages
69 - 73
Database
ISI
SICI code
0020-0190(1994)50:2<69:MCOHQC>2.0.ZU;2-S
Abstract
The hierarchical quorum consensus (HQC) algorithm, which is a generali zation of the standard quorum consensus algorithm for managing replica ted data, can reduce the quorum size to N0.63. This paper analyzes the message complexity of HQC. Moreover, an asymptotic analysis on the ra tio of the message complexity to the quorum size is presented. It is s hown that the ratio converges to a constant.