A geometric approach for constructing coteries and k-coteries
- 1 April 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 8 (4) , 402-411
- https://doi.org/10.1109/71.588618
Abstract
[[abstract]]Quorum-based mutual exclusion algorithms are resilient to node and communication line failures. Recently, some mutual exclusion algorithms successfully use logical structures to construct coteries with small quorums sizes, In this paper, we introduce a geometric approach on dealing with the logical structures and present some useful geometric properties for constructing coteries and k-coteries. Based on those geometric properties, a logical structure named three-sided graph is proposed to provide a new scheme for constructing coteries with small quorums: The smallest quorum size is O(root N) in a homogeneous system with N nodes and O(1) in a heterogeneous system. In addition, we also extend the three-sided graph to the n-sided graph for constructing k-coteries.[[fileno]]2030249010025[[department]]資訊工程學This publication has 11 references indexed in Scilit:
- k-coteries for fault-tolerant k entries to a critical sectionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An efficient method for mutual exclusion in truly distributed systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Another distributed algorithm for multiple entries to a critical sectionInformation Processing Letters, 1992
- The grid protocol: a high performance scheme for maintaining replicated dataIEEE Transactions on Knowledge and Data Engineering, 1992
- Hierarchical quorum consensus: a new algorithm for managing replicated dataIEEE Transactions on Computers, 1991
- An efficient and fault-tolerant solution for distributed mutual exclusionACM Transactions on Computer Systems, 1991
- A distributed algorithm for multiple entries to a critical sectionInformation Processing Letters, 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