Show simple item record

dc.contributor.authorWright, David D.en_US
dc.contributor.authorSkeen, Daleen_US
dc.description.abstractPartitioning 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 probabilistic model is presented and compared with the simulations.en_US
dc.format.extent1497924 bytes
dc.format.extent384635 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleMerging Partitioned Databasesen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record