A graphical approach to allocating class fragments in distributed objectbase systems

This paper contributes by providing an allocation taxonomy to analyze DOBS models and identify the primary characteristics of a DOBS allocation. A gra phical optimization technique, based on the work by Kernighan and Lin (The Bell System, Technical Journal, pp. 291-307, 1970), is basis of our approac h. The algorithm attempts to arrive at a "near optimal" distribution of fra gments by exchanging and/or moving fragments between every pair of sites. T he algorithms are implemented and are tested with carefully generated test data to obtain an analysis of the performance. The design, implementation a nd analysis of the allocation algorithms form the most significant contribu tion of this paper. Several significant insights are derived from the analy sis of the results obtained that can be usefully applied to any real life D OBS allocation design. The applicability of the allocation algorithms for t he DOBS model of interest may be verified by a cost benefit analysis based on their efficiency. The optimization of the initial allocation is meaningf ul only if the improvement obtained by optimization justifies the additiona l overhead. If significant improvement is not obtainable by optimization th en our efficient initial allocation scheme alone may serve the purpose.