A simple scheme to constructk‐arbiters with uniform quorum sizes
Yu‐Chen Kuo · Journal of the Chinese Institute of Engineers · 2003
k‐Arbiter is a useful concept for solving the distributed h‐out of‐k mutual exclusion problem. The distributed h‐out of‐k mutual exclusion algorithms based on k‐arbiter have the benefits of high fault‐tolerance and low message cost. However, according to the definition of k‐arbiter, it is required to have a non‐empty intersection among any (k+1) quorums in a k‐arbiter. Consequently, constructing k‐arbiters is difficult. In this paper, we propose a simple scheme to construct k‐arbiters for any integer k. The constructed k‐arbiters, named binomial(q, k)‐arbiters, are uniform: each quorum in a k‐arbiter has the same size and each node contains the same number of quorums. Also, the constructed k‐arbiters perform better than other known k‐arbiters do on quorum size and availability.