David Shou and Sheng-De Wang
Department of Electrical Engineering
National Taiwan University
Taipei, Taiwan 106, R.O.C.
This paper describes a new quorum generating method to solve the distributed mutual exclusion prThe conventional quorum consensus methods are expensive due to their high communication cost. Recently, several structures employed in quorum schemes have successfully reduced quorum size. These studies motivated us to investigate the possibility of further reducing quorum size while preserving desirable features. Our approach logically organizes nodes in a network into a multilevel structure to generate quorums, called level quorums. The level quorums can be of constant size and, thus, incur a constant communication cost in a reliable system and degrade gracefully as failures increase. Tradeoffs between ours and five other quorum-based methods are discussed. Also, an application of level quorums is proven to be superior to a high performance scheme, the grid quorum.
Keywords: availability, distributed systems, mutual exclusion, quorum consensus, replication, voting
Received July 10, 1992; revised March 23, 1993.
Communicated by Wen-Tsuen Chen.