Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.3, pp.615-631 (July 2001)

k-Arbiter Join Operation*


Yu-Chen Kuo

Department of Computer and Information Science
SooChow University
Taipei, Taiwan 100, R.O.C.
E-mail: yckuo@cis.scu.edu.tw

k-Arbiter is a useful concept for solving the distributed h-out of-k resources allocation problem. The distributed h-out of-k resources allocation algorithms based on k-arbiter have the benefits of high fault-tolerance and low communication 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. The coterie join operation proposed by Neilsen and Mizuno produces a new and larger coterie by joining known coteries. In this paper, by extending the coterie join operation, we first propose a k-arbiter join operation to construct a new and larger k-arbiter from known k-arbiters. Then, we derive a necessary and sufficient condition for the k-arbiter join operation to construct a nondominated composite k-arbiter. Moreover, we discuss the availability properties of the composite k-arbiters. We observe that by selecting the proper k-arbiters as join inputs, the composite k-arbiter can have a higher availability than that of the original inputs.

Keywords: distributed systems, fault-tolerance, h-out of-k resources allocation, quorums, mutual exclusion

Full Text () Retrieve PDF document (200107_05.pdf)

Received March 13, 2000; revised June 29 & July 26, 2000; accepted August 16, 2000.
Communicated by Chu-Sing Yang
*This research was supported in part by the National Science Council of the Republic of China under Grant No. NSC 88-2213-E-031-004.