Tech Report CS-93-43

An Efficient Scheme for Dynamic Data Replication

Swarup Acharya and Stanley B. Zdonik

September 1993


This paper presents an efficient scheme for dynamic replication of data in distributed environments. The aim of the scheme is to increase system performance by intelligent data placement so as to optimize the message traffic in the network. Research in the recent past has comparatively focussed very little on using replication for increasing performance but has instead been directed more at improving system availability through replication. However, with the advent of mobile or nomadic computing, research in replication needs to change direction-- the underlying assumption of high speed networks no longer hold true. Wireless networks not only have lower bandwidth but are also very expensive to use. In such an environment, it is imperative that data be distributed intelligently to achieve a good system performance in terms of message costs and turnaround time. Besides, with mobility introduced in the system, earlier static schemes for improving performance (e.g., the File Allocation Problem) are no longer applicable. As a first step, we propose a totally distributed dynamic replication scheme, which uses a finite automaton based technique to learn access patterns. This accrued information is then used to predict future access sequences and dynamically reorder-- replicate or delete copies of data in the network, in anticipation of predicted accesses, to reduce network message costs. Being distributed, each node of the network bases its decision to replicate or delete an existing copy solely on local information. Our algorithm is also integrated and corrects some of the drawbacks of earlier theoretical work in this area. Finally, we present some preliminary simulation results which show that our scheme is very promising.

(complete text in pdf or gzipped postscript)