Boolean theory of coteries
- 10 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 150-157
- https://doi.org/10.1109/spdp.1991.218285
Abstract
A coterie under a ground set U consists of a set of subsets (quorums) of U such that any pair of quorums intersect each other. 'Nondominated' coteries are of particular interest, since they are 'optimal' in some sense. By assigning a Boolean variable to each element in U, we represent a coterie by a Boolean function of these variables. The authors characterize the nondominated coteries as exactly those which can be represented by positive, self-dual functions. They take advantage of Boolean decomposition theorems to investigate 'decomposition' (or 'composition') of coteries, and prove that any function representing a nondominated coteries can be composed from copies of the 3-majority function. They also introduce a 'decomposition tree' to represent any nondominated coterie. A number of other new results are also obtained, demonstrating the usefulness of the Boolean approach.Keywords
This publication has 8 references indexed in Scilit:
- Coterie join algorithmIEEE Transactions on Parallel and Distributed Systems, 1992
- Optimizing vote and quorum assignments for reading and writing replicated dataIEEE Transactions on Knowledge and Data Engineering, 1989
- Efficient solution to the distributed mutual exclusion problemPublished by Association for Computing Machinery (ACM) ,1989
- How to assign votes in a distributed systemJournal of the ACM, 1985
- A √N algorithm for mutual exclusion in decentralized systemsACM Transactions on Computer Systems, 1985
- A Majority consensus approach to concurrency control for multiple copy databasesACM Transactions on Database Systems, 1979
- Threshold Logic AsymptotesIEEE Transactions on Computers, 1970
- A Lower Bound of the Number of Threshold FunctionsIEEE Transactions on Electronic Computers, 1965