On Merging Partitioned Databases.

David D. Wright: On Merging Partitioned Databases. SIGMOD Conference 1983: 6-14

@inproceedings{DBLP:conf/sigmod/Wright83,
  author    = {David D. Wright},
  editor    = {David J. DeWitt and
               Georges Gardarin},
  title     = {On Merging Partitioned Databases},
  booktitle = {SIGMOD'83, Proceedings of Annual Meeting, San Jose, California,
               May 23-26, 1983},
  publisher = {ACM Press},
  year      = {1983},
  pages     = {6-14},
  ee        = {http://doi.acm.org/10.1145/582192.582199, db/conf/sigmod/Wright83.html},
  crossref  = {DBLP:conf/sigmod/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

Copyright © 1983 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

David J. DeWitt, Georges Gardarin (Eds.): SIGMOD'83, Proceedings of Annual Meeting, San Jose, California, May 23-26, 1983. ACM Press 1983 BibTeX , SIGMOD Record 13(4)
Contents

Online Edition: ACM Digital Library

References

[AHU74]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[Davi82]: ...
[Giff79]: David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[GaJo79]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[Lova75]: ...
[Thom78]: ...
[WrSk84]: ...

Referenced by

Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
Sushil Jajodia: Managing Replicated Files in Partitioned Distributed Database Systems. ICDE 1987: 412-418

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]