A Static Pessimistic Scheme for Handling Replicated Databases.

Jian Tang, N. Natarajan: A Static Pessimistic Scheme for Handling Replicated Databases. SIGMOD Conference 1989: 389-398
  author    = {Jian Tang and
               N. Natarajan},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {A Static Pessimistic Scheme for Handling Replicated Databases},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {389-398},
  ee        = {, db/conf/sigmod/TangN89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP,}


A replicated database system may partition into isolated groups in the presence of node and link failures. When the system has partitioned, a pessimistic scheme maintains availability and consistency of replicated data by ensuring that updates occur in at most one group. A pessimistic scheme is called a static scheme if these distinguished groups are determined only by the membership of different groups in the partitioned system. In this paper, we present a new static scheme that is more powerful than voting. In this scheme, the set of distinguished groups, called an acceptance set, is chosen at design time. To commit an update, a node checks if its enclosing group is a member of this acceptance set. Using an encoding scheme for groups, this check is implemented very efficiently. Another merit of the proposed scheme is that the problem of determining an optimal acceptance set is formulated as a sparse O-1 linear programming problem. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Based on our experiments, we feel that this optimization approach is feasible for systems containing up to 10 nodes (copies).

Copyright © 1989 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 ...

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

Printed Edition

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989

Online Edition: ACM Digital Library


Susan B. Davidson, Hector Garcia-Molina, Dale Skeen: Consistency in Partitioned Networks. ACM Comput. Surv. 17(3): 341-370(1985) BibTeX
Hector Garcia-Molina, Daniel Barbará: How to Assign Votes in a Distributed System. J. ACM 32(4): 841-860(1985) BibTeX
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238 BibTeX
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
Zhijun Tong, Richard Y. Kain: Vote Assignments in Weighted Voting Mechanisms. IEEE Trans. Computers 40(5): 664-667(1991) BibTeX

Referenced by

  1. Nabil R. Adam: A New Dynamic Voting Algorithm for Distributed Database Systems. IEEE Trans. Knowl. Data Eng. 6(3): 470-478(1994)
  2. Jian Tang, N. Natarajan: Obtaining Coteries That Optimize the Availability of Replicated Databases. IEEE Trans. Knowl. Data Eng. 5(2): 309-321(1993)
  3. Divyakant Agrawal, Amr El Abbadi: Storage Efficient Replicated Databases. IEEE Trans. Knowl. Data Eng. 2(3): 342-352(1990)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:59 2009