A geometric approach for constructing coteries and k-coteries

Author

Kuo, Yu-Chen ; Huang, Shing-Tsaan

Author_Institution

Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan

Volume

8

Issue

4

fYear

1997

fDate

4/1/1997 12:00:00 AM

Firstpage

402

Lastpage

411

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(√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 O-sided graph for constructing k-coteries

Keywords

distributed algorithms; fault tolerant computing; multiprocessor interconnection networks; trees (mathematics); O-sided graph; communication line failures; coteries; geometric approach; k-coteries; logical structure; mutual exclusion algorithms; quorum-based mutual exclusion algorithms; three-sided graph; Algorithm design and analysis; Cascading style sheets; Costs; Distributed algorithms; Fault tolerance; Helium; Permission; Senior members; Tree graphs; Voting;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.588618

Filename

588618