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.