Hu, Ping; (1993) Dynamic supporting: An efficient method for replicated file systems. Doctoral thesis (Ph.D), UCL (University College London).

Text Dynamic_supporting_An_efficie.pdf Download (9MB)

Abstract

In a distributed computing system, files can be replicated to improve performance. One-copy serializability is widely accepted as a correctness criterion for a replicated file system. In the light of trade-off between consistency and availability, file replication strategies can be classified into two groups: optimistic and pessimistic. In this dissertation, a new pessimistic strategy is proposed for maintaining the mutual consistency of replicated file systems. Unlike most conventional voting algorithms, votes are no longer attached to replicas in the proposed strategy. The strategy includes a basic algorithm, called dynamic supporting, which uses a policy like the available copies algorithm to maintain replicas and uses a modified dynamic voting algorithm to support those replicas, and thus maintains the one-copy serializability in the presence of network partitioning. The dynamic supporting algorithm is extended to dynamic supporting algorithm with a greatest copy (dynamic supporting(G) algorithm, for short) to increase availability and other performance parameters. These two algorithms are hybrids of some existing algorithms, and are designed to combine the advantages of those algorithms. Since replicas and votes are conceptually separated, the algorithms can achieve very good performance while still keeping storage cost for file replication very low, especially only two replicas for each logical file. The proposed algorithms are very efficient and simple to run. In the algorithms, any operation on a logical file will never be blocked as long as all the replicas of this logical file are available. If one or more replicas are not accessible, the votes for the logical file will be used by a special scheme to support those accessible replicas so that the one-copy serializability is ensured. Availability and reliability are most widely used performance measures for replicated file systems. Both measures for the dynamic supporting algorithms and other file replication algorithms are evaluated and compared in this dissertation. A system model is proposed for stochastic analysis of such measures. Under this model, the behaviour of a given algorithm can be presented by a Markovian chain or process so that availability or reliability can be evaluated by solving a set of linear equations or linear differential equations, respectively. Simulation is conducted as a complement and extension to the stochastic analysis. The system model for simulation is presented and discussed as more reality is considered and put into the model for stochastic analysis. The system model for stochastic analysis can be viewed as an extreme case of the system model for simulation. Both of the stochastic analysis results and simulation results show that availability and reliability for the dynamic supporting algorithm and dynamic supporting(G) algorithm are much better than other algorithms, and very close to the available copies algorithm, which is usually regarded as the best in respect to these performance measures. Other performance measures that affect the efficiency in a replicated file system, such as network traffic incurred by file replication and transaction execution and processing time, are also analysed. The advantages of the proposed pessimistic strategy are shown in the dissertation. The dynamic supporting algorithm and the dynamic supporting(G) algorithm are more attractive than other algorithms because both of them can achieve very high availability and reliability and also tolerate network partition failures while still keeping other overhead costs for file replication very low.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item