Abstract
Quorum systems have been used to implement many coordination problems in distributed systems. In this paper, we study the cost of accessing quorums in asynchronous systems. We formally define the asynchronous access cost of quorum 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 quorums in asynchronous systems. We show that previous quorum systems proposed 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 quorum systems proposed in the literature. In particular, we present a construction for the disjoint failure pattern that outperforms previously proposed systems for that pattern.
Original language | English (US) |
---|---|
Pages (from-to) | 41-48 |
Number of pages | 8 |
Journal | Distributed Computing |
Volume | 14 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2001 |
Keywords
- Access cost
- Asynchronous
- Byzantine failures
- Distributed systems
- Fault tolerance
- Quorum
ASJC Scopus subject areas
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computational Theory and Mathematics