Lecture Notes in Computer Science, 2001, Volume 2180/2001, 16-32, DOI: 10.1007/3-540-45414-4_2

Quorum-Based Algorithms for Group Mutual Exclusion

Yuh-Jzer Joung

View Related Documents

Abstract

We propose a quorum system, which we referred to as the surficial quorum system, for group mutual exclusion. The surficial quorum system is geometrically evident and so is easy to construct. It also has a nice structure based on which a truly distributed algorithm for group mutual exclusion can be obtained, and processes’ loads can be minimized. When used with Maekawa’s algorithm, the surficial quorum system allows up to $ \sqrt {\frac{{2n}} {{m\left( {m - 1} \right)}}} $ \sqrt {\frac{{2n}} {{m\left( {m - 1} \right)}}} processes to access a resource simultaneously, where n is the total number of processes, and m is the total number of groups. We also present two modifications of Maekawa’s algorithm so that the number of processes that can access a resource at a time is not limited to the structure of the underlying quorum system, but to the number that the problem definition allows.
Part of this research was done when the author was visiting Lab for Computer Science, Massachusetts Institute of Technology (1999–2000). Research supported in part by the National Science Council, Taipei, Taiwan, Grants NSC 89-2213-E-002- 110

Fulltext Preview

Image of the first page of the fulltext document