Sizes of a Symmetric Coterie

概要

論文の詳細を見る
A coterie is a set of subsets in which any two of the subsets intersect and in which no subset contains any other subset. A subset is called a quorum. Coteries are used in many distributed algorithms such as distributed mutual exclusion and replicated data management. For distributed algorithms, symmetric coteries are desirable because they realize equal distribution of load, responsibility, and information. In this paper, we show that a lower bound of the quorum size of a symmetric coterie, whose quorum sizes are the same and in which each node appears in the same number of quorums, is √<n>, where n is the number of nodes. When a further condition is added, specifying that the size of the intersection of two distinct quorums is always 1, an upper bound of the coterie size of a symmetric coterie is n. It is also shown that a finite projective plane is an optimal symmetric coterie.
一般社団法人情報処理学会の論文
1995-06-15