On merging partitioned databases

ABSTRACT

Partitioning of a distributed data base requires either that update activity be restricted or that a strategy for conflict resolution and partition merging be used once communication is restored. The graph-theoretic approach used by Davidson follows the latter approach and can be used to show that finding an optimum solution to the general problem is NP-complete. We give several methods of reducing the size of the graphs involved. Two open subproblems are shown to be NP-complete, while an extension of a known polynomial-time subproblem is given. Simulation results are used to study both the amount of compression achieved by the graph reduction techniques and their effects on heuristics for the problem. In addition, some modifications are made to existing heuristics to improve their performance. A simple probabilistic model is developed and compared to the simulation results.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Susan B. Davidson, An optimistic protocol for partitioned distributed database systems, 1982
• 3: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 4: {GaJo79} Garey, M.R., and D.S. Johnson, Computers and Intractability, W.H. Freeman & Co., 1979.
• 5: {Lova75} Lovasz, L., "Three Short Proofs in Graph Theory", J. Combinatorial Theory B, 19, 111--113.
• 6: {Thom78} Thomas, R.H., "A Solution to the Concurrency Control Problem for Multiple Copy Databases," IEEE Compcon, Spring 1978, pp.56--62.
• 7: David D. Wright , Dale Skeen, Merging Partitioned Databases, Cornell University, Ithaca, NY, 1983