AN O(ROOT-N) ALGORITHM FOR CONCURRENCY-CONTROL IN REPLICATED FILE-SYSTEMS

Authors
GAVISH B GERDES JH SRIDHAR S SRINIVASAN KA
Citation
B. Gavish et al., AN O(ROOT-N) ALGORITHM FOR CONCURRENCY-CONTROL IN REPLICATED FILE-SYSTEMS, INFOR. Information systems and operational research, 35(1), 1997, pp. 1-14
Citations number
19
Categorie Soggetti
Operatione Research & Management Science
Journal title
INFOR. Information systems and operational research → ACNP
ISSN journal
03155986
Volume
35
Issue
1
Year of publication
1997
Pages
1 - 14
Database
ISI
SICI code
0315-5986(1997)35:1<1:AOAFCI>2.0.ZU;2-5
Abstract
The problem of ensuring mutual exclusion in a distributed, replicated file system is investigated. An O(root N) algorithm is presented to so lve the above problem and its correctness is proved. The nodes in the system are partitioned into mutually disjoint sets. By partitioning no des appropriately, it is shown that a write quorum can be formed with 2 root N-1 copies, while a read quorum requires only root N copies. Co mparisons are presented relating this algorithm to previous work. Mech anisms for handling the failures of links and sites are also proposed.