ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Sacrificing Serializability to Attain High Availability of Data.

Michael J. Fischer, A. Michael: Sacrificing Serializability to Attain High Availability of Data. PODS 1982: 70-75
@inproceedings{DBLP:conf/pods/FischerM82,
  author    = {Michael J. Fischer and
               A. Michael},
  title     = {Sacrificing Serializability to Attain High Availability of Data},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {70-75},
  ee        = {http://doi.acm.org/10.1145/588111.588124, db/conf/pods/FischerM82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present a simple algorithm for maintaining a replicated distributed dictionary which achieves high availability of data, rapid processing of atomic actions, efficient utilization of storage, and tolerance to node or network failures including lost or duplicated messages. It does not require transaction logs, synchronized clocks, or other complicated mechanisms for its operation. It achieves consistency contraints which are considerably weaker than serial consistency but nonetheless are adequate for many dictionary applications such as electronic appointment calendars and mail systems. The degree of consistency achieved depends on the particular history of operation of the system in a way that is intuitive and easily understood. The algorithm implements a "best effort" approximation to full serial consistency, relative to whatever internode communication has successfully taken place, so the semantics are fully specified even unter partial failure of the system. Both the correctness of the algorithm and the utility of such weak semantics depend heavily on special properties of the dictionary operations.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
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
[2]
Philip A. Bernstein, James B. Rothnie Jr., Nathan Goodman, Christos H. Papadimitriou: The Concurrency Control Mechanism of SDD-1: A System for Distributed Databases (The Fully Redundant Case). IEEE Trans. Software Eng. 4(3): 154-168(1978) BibTeX
[3]
Philip A. Bernstein, David W. Shipman, Wing S. Wong: Formal Aspects of Serializability in Database Concurrency Control. IEEE Trans. Software Eng. 5(3): 203-216(1979) BibTeX
[4]
Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX
[5]
Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[6]
Hector Garcia-Molina, Gio Wiederhold: Read-Only Transactions in a Distributed Database. ACM Trans. Database Syst. 7(2): 209-234(1982) BibTeX
[7]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[8]
Michael Hammer, David W. Shipman: Reliability Mechanisms for SDD-1: A System for Distributed Databases. ACM Trans. Database Syst. 5(4): 431-466(1980) BibTeX
[9]
...
[10]
...
[11]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19: 1-11(1983) BibTeX
[12]
...
[13]
...
[14]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[15]
...
[16]
...
[17]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[18]
Gerald J. Popek, Bruce J. Walker, Johanna M. Chow, David A. Edwards, Gerard Rudisin, Greg Thiel: LOCUS - A Network Transparent, High Reliability Distributed System. SOSP 1981: 169-177 BibTeX
[19]
Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: Consistency and Serializability in Concurrent Database Systems. SIAM J. Comput. 13(3): 508-530(1984) BibTeX
[20]
James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, Terry A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX
[21]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

Referenced by

  1. Ouri Wolfson, Sushil Jajodia, Yixiu Huang: An Adaptive Data Replication Algorithm. ACM Trans. Database Syst. 22(2): 255-314(1997)
  2. Divyakant Agrawal, Amr El Abbadi, Robert C. Steinke: Epidemic Algorithms in Replicated Databases (Extended Abstract). PODS 1997: 161-172
  3. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
  4. O. T. Satyanarayanan, Divyakant Agrawal: Efficient Execution of Read-Only Transactions in Replicated Multiversion Databases. IEEE Trans. Knowl. Data Eng. 5(5): 859-871(1993)
  5. P. C. Aristides, Amr El Abbadi: Fast Read-Only Transactions in Replicated Databases. ICDE 1992: 246-253
  6. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance in Replicated Systems. PODS 1991: 63-74
  7. Sushil Jajodia, David Mutchler: Dynamic Voting Algorithms for Maintaining the Consistency of a Replicated Database. ACM Trans. Database Syst. 15(2): 230-280(1990)
  8. Partha Dasgupta, Zvi M. Kedem: The Five Color Concurrency Control Protocol: Non-Two-Phase Locking in General Databases. ACM Trans. Database Syst. 15(2): 281-307(1990)
  9. Divyakant Agrawal, Amr El Abbadi: Storage Efficient Replicated Databases. IEEE Trans. Knowl. Data Eng. 2(3): 342-352(1990)
  10. Divyakant Agrawal, Amr El Abbadi: Reducing Storage for Quorum Consensus Algorithms. VLDB 1988: 419-430
  11. Maurice Herlihy: Dynamic Quorum Adjustment for Partitioned Data. ACM Trans. Database Syst. 12(2): 170-194(1987)
  12. Sushil Jajodia, David Mutchler: Dynamic Voting. SIGMOD Conference 1987: 227-238
  13. Gio Wiederhold, Xiaolei Qian: Modeling Asynchrony in Distributed Databases. ICDE 1987: 246-250
  14. Sushil Jajodia, Catherine Meadows: Mutual Consistency in Decentralized Distributed Systems. ICDE 1987: 396-404
  15. Sushil Jajodia: Managing Replicated Files in Partitioned Distributed Database Systems. ICDE 1987: 412-418
  16. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
  17. Sunil K. Sarin, Charles W. Kaufman, Janet E. Somers: Using History Information to Process Delayed Database Updates. VLDB 1986: 71-78
  18. Barbara T. Blaustein, Charles W. Kaufman: Updating Replicated Data During Communications Failures. VLDB 1985: 49-58
  19. Alexander Tuzhilin, Paul G. Spirakis: A Semantic Approach to Correctness of Concurrent Transaction Executions. PODS 1985: 85-95
  20. Nathan Goodman, Dale Skeen, Arvola Chan, Umeshwar Dayal, Stephen Fox, Daniel R. Ries: A Recovery Algorithm for a Distributed Database System. PODS 1983: 8-15
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:39 2009