Access cost for asynchronous Byzantine quorum systems

Authors
Citation
Ra. Bazzi, Access cost for asynchronous Byzantine quorum systems, DIST COMPUT, 14(1), 2001, pp. 41-48
Citations number
17
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
DISTRIBUTED COMPUTING
ISSN journal
0178-2770 → ACNP
Volume
14
Issue
1
Year of publication
2001
Pages
41 - 48
Database
ISI
SICI code
0178-2770(200101)14:1<41:ACFABQ>2.0.ZU;2-8
Abstract
Quorum systems have been used to implement many coordination problems in di stributed systems. In this paper, we study the cost of accessing quorums in asynchronous systems. We formally define the asynchronous access cost of q uorum systems and argue that the asynchronous access cost and not the size of a quorum is the right measure of message complexity of protocols using q uorums in asynchronous systems. We show that previous quorum systems propos ed in the literature have a very high asynchronous access cost. We propose a reformulation of the definition of Byzantine quorum systems that captures the requirement for non-blocking access to quorums in asynchronous systems . We present new Byzantine quorum systems with low asynchronous access cost whose other performance parameters match those of the best Byzantine quoru m systems proposed in the literature. In particular, we present a construct ion for the disjoint failure pattern that outperforms previously proposed s ystems for that pattern.