Raw bibliography

These are papers that might be of some interest, not categorized at all.  The "annotations" may just be to help me (Demers) remember what paper this is, and may reflect just a superficial reading.  Some links are to copies I have cached, I believe legally.  Others go to the Web and may eventually dangle.

[AAE+96]  D. Agrawal, G. Alonso, A. El Abbadi and I. Stanoi.  Exploiting atomic broadcast in replicated databases.  Technical report, Swiss Federal Institute of Technology, 1996.

Early paper on replacing database atomic commitment with atomic broadcast.  See [PGS98b].

[AAF+95] S. Acharya , R. Alonso , M. Franklin , and S. Zdonik.  Broadcast Disks: Data Management for Asymmetric Communications Environments. SIGMOD Conference, 1995. 

[ABE+93]  D. Agrawal, J. Bruno, A. El Abbadi and V. Krishnaswamy.  Relative serializability: an approach for relaxing the atomicity of transactions.

Extends [FO89] so recognizing the safe schedules (called relatively serializable rather than relatively consistent) is no longer NP-complete.

[ACT00]  M. Aguilera, W. Chen and S. Toueg.  Failure detection and consensus in the crash-recovery model.  Distributed Computing 13, 2000.

[AFZ96] S. Acharya , M.. Franklin and S. Zdonik.  Disseminating Updates on Broadcast Disks. Proceedings 22nd VLDB Conference, 1996.

[AFZb96] S. Acharya, M. Franklin and S. Zdonick.  Prefetching from a Broadcast Disk.  Proceedings International Conference on Data Engineering, Feb. 1996.

[BG94] D. Barbara-Milla and H. Garcia-Molina.  The Demarcation Protocol: A Technique for Maintaining Constraints in Distributed Database Systems.  VLDB Journal 3(3), 1994.

[BK97]  Y. Breitbart and H. Korth.  Replication and consistency: being lazy helps sometimes.  Proceedings 1997 PODS Conference.

Introduces the virtual site abstraction to get 1SR in a lazy master system for single-site transactions.  Also a description of a protocol sketched in [GHOS96] that achieves 1SR in a lazy master system at the cost of some distributed locking.

[BKR+99]  Y. Breitbart, R. Komondoor, R. Rastogi, S. Seshadri, A. Silberschatz.  Update propagation protocols for replicated databases.  Proceedings 1999 SIGMOD Conference, May 1999.

Extends [CRR96] by relaxing placement restrictions (from undirected acyclic to DAG).  Weaker than [CRR96b] in that transactions must be single-site; but does not require any eager propagation (distributed transactions).  A further extension eliminates all placement restrictions but involves a mixture of lazy and eager propagation.

[BR92]  B. Badrinath and K. Ramamritham.  Semantics-based concurrency control: beyond commutativity.  ACM TODS 17(1), March 1992.

Introduces recoverability of operations, generalizes commutativity and allows more schedules to be shown serializable.

[CRR96]  P. Chundi, D. Rosenkrantz, and S. Ravi.  Deferred update protocols and data placement in distributed databases.  Proceedings 12th ICDE, 1996.

Guarantees 1SR in lazy-master system, with substantial restrictions on assignment of masters to data objects and with single-site transactions.

[CRR96b]  P. Chundi, D. Rosenkrantz, and S. Ravi.  Deferred update protocols for multi-site transactions.  Proceedings 1996 VLDB, 1996.

Extends previous paper [CRR96] to multi-site transactions.

[CT96]  T. Chandra and S. Toueg.  Unreliable failure detectors for reliable distributed systems.  JACM, 43(2), March 1996.

[DGH+87]  A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart and D. Terry.  Epidemic Algorithms for Replicated Database Maintenance.  Proceedings of the Sixth Annual ACM Symposium on Principles of distributed computing, 1987.

What can I say?

[DGS85]  S. Davidson, H. Garcia-Molina, and D. Skeen.  Consistency in partitioned networks.  ACM Computing Surveys 17(3), September 1985.

High-level survey of consistency issues when operation continues during a partition.  Discusses some anomalies that are worth remembering.  An easy read.

[DVCK99] A. Datta, D. Vandermeer, A. Celik and V. Kumar.  Broadcast Protocols to Support Efficient Retrieval from Databases by Mobile Users.  ACM Transactions on Database Systems 24(1), March 1999.

[FGL+96]  A. Fekete, D. Gupta, V. Luchangco, N. Lynch and A. Shvartsman.  Eventually-Serializable Data Services.  Proceedings of the Fifteenth ACM Symposium on the Principles of Distributed Computing, 1996.

Formalization heavily based on [LLSG92].

[FO89]  A. Farrag and M. Ozsu.  Using semantic knowledge of transactions to increase concurrency.  ACM TODS 14(4), December 1989.

Transaction interleavings specified by breakpoints; definition of relatively consistent schedules that cannot violate consistency.  Unfortunately, recognizing relatively consistent executions is NP-complete.  But see [ABE+93].  Motivated by concurrency performance rather than replication.

[G83] H. Garcia-Molina.  Using semantic knowledge for transaction processing in a distributed database.  ACM TODS 8(2), June 1983.

A seminal paper.  Suggests transaction types, compatibility sets that specify allowable interleavings.  More for increasing concurrency in distributed database than for replication; it's not completely clear how to use this approach for replication.

[G92]  R. Golding.  Weak-consistency group communication and membership.  Thesis, UCSC, 1992.  See also Golding's home page.

The authoritative version of "timestamped anti-entropy" (TSAE).  Compare with the MIT "lazy replication" work [LLSG92] and the Bayou protocols, especially node creation and retirement.  A good thing to have read.

[G95]  R. Guerraoui.  Revisiting the relationship between non-blocking atomic commitment and consensus.  Proceedings of the International Workshop on Distributed Algorithms, 1995.

Impossibility of nonblocking atomic commitment in asynchronous systems with unreliable failure detectors; solvability of weak nonblocking atomic commitment, which (roughly) replaces the "no failure" part of the nontriviality condition of commitment with "no suspected failure."  Why is this relevant?  Because of claims about relative performance of protocols based on atomic broadcast variants vs those based on (weak) nonblocking atomic commit. 

[GHM+00] R. Guerraoui, M. Hurfin, A. Mostefaoui, R. Oliveira, M. Raynal and A. Schiper.  Consensus in Asynchronous Distributed Systems: A Concise Guided Tour.  In Advances in Distributed Systems, Springer-Verlag LNCS 1752, 2000.

[GHOS96]  J. Gray, P. Helland, P. O'Neil and D. Shasha.  The dangers of replication and a solution.  Proceedings 1996 SIGMOD Conference, June 1996.

Introduces the {eager,lazy} + {group,master} classification.  Plausible but (I claim) misleading analyses of scaling behavior of replicated data bases.  Proposes a hierarchical replication scheme.  Compare this with Oracle snapshots (now "materialized views") and the Bayou tentative/committed distinction.

[Gol95] R. Goldring.  Things every update replication customer should know.  Proceedings 1995 SIGMOD Conference, June 1995.

Examples of nonserializable behavior in lazy systems.

[GS97]  R. Guerraoui and A. Schiper. Consensus: the big misunderstanding. Proceedings of the 6th IEEE Computer Society Workshop on Future Trends in Distributed Computing Systems, October 1997.

[HGL+87] G. Herman, G. Fopal, K. C. Lee and A. Weinrib.  The Datacycle Architecture for Very High Throughput Database Systems.  Proceedings ACM SIGMOD Conference, 1987.

[HSAE99] J. Holliday, R. Steinke, D. Agrawal, A. El Abbadi.  Epidemic Quorums for Managing Replicated Data. UCSB Computer Science Department Technical Report TRCS99-32, October 1999.

Technique for 1SR with deferred update propagation.  Uses gossip protocol with vector timestamps to guarantee causal ordering.  Quorum used for abort decisions on conflicting txns.  Uses n**2 metadata exchanges for stability detection.  Is this practical?  Simulation results based on 2 millisecond gossip rounds.

[IB94] Imielinski, T. and B. Badrinath.  Mobile wireless computing: solutions and challenges in data management.  CACM 37(10), Oct 1994.

[IVB94] Imielinski, T., S. Vishwanath and B. Badrinath.  Energy efficient indexing on air.  Proceedings ACM SIGMOD Conference, 1994.

[IVBb94] Imielinski, T., S. Vishwanathan and B. Badrinath.  Power efficient filtering of data on air.  Proceedings 4th International Conference on Extending Database Technology: Advances in Database Technology (EDBT 94).

[KA98]  B. Kemme and G. Alonso.  A suite of database replication protocols based on group communication primitives.  Proceedings ICDCS, 1998.

Suite of protocols using various delivery guarantees and various degrees of isolation.

[KA00]  B. Kemme and G. Alonso.  Don't be lazy, be consistent: Postgres-R, a new way to implement database replication.  Proceedings 26th VLDB Conference, 2000.

Implementation results basically for protocols described in [KA98].

[KR81]  H. Kung and J. Robinson.  On optimistic methods for concurrency control.  ACM TODS 6(2), June 1981.

Old but classic reference on optimistic CC.

[LCW97] D. Lam, D. Cox and J. Widom.  Teletraffic Modeling for Personal Communications Services.   IEEE Communications 35(2), February 1997.

[LS94] Q. Lu and M. Satyanaranyanan.  Isolation-Only Transactions for Mobile Computing.  ACM Operating Systems Review, April 1994.

[LS95] Q. Lu and M. Satyanaranyanan.  Improving Data Consistency for Mobile Computing Using Isolation-Only Transactions.  Proceedings 5th HotOS Conference, May 1995.

[L96] Q. Lu.  Improving Data Consistency for Mobile File Access Using Isolation-Only Transactions.  Ph.D. Thesis, CMU-CS-96-131, 1996.

[LLSG92]  R. Ladin, B. Liskov, L. Shrira, and S. Ghemawat. Providing high availability using lazy replication. ACM Transaction on Computer Systems, 10(4):360, November
1992.

Epidemic protocol providing causal guarantees (or stronger, at higher cost).

[Mariposa] Home page of the (now defunct) Mariposa project at UCB.

[NFC00] B. Noble, B. Fleis and L. Cox.  Deferring Trust in Fluid Replication.  9th ACM SIGOPS European Workshop, Sept 2000.

[NFK99] B. Noble, B. Fleis and M. Kim.  A Case for Fluid Replication.  Proceedings NetStore 1999.

[NFKZ99] B. Noble, B. Fleis, M. Kim and J. Zajkowski.  Fluid Replication.  Proceedings NetStore 1999.

Note that [NFK99] and [NFKZ99] are not identical; [NFK99] is the one that appears at the conference site, and seems more complete.

[OGS97]  R. Oliviera, R. Guerraoui and A. Schiper.  Consensus in the crash-recover model.  Technical report TR97-239, EPFL, Computer Science Department, 1997.

[OW99] C. Olson and J. Widom.  Offering a Precision-Performance Tradeoff for Aggregation Queries Over Replicated Data.

[P99]  F. Pedone.  The Database State Machine and Group Communication Issues.  Thesis, Ecole Polytechnique Federale de Lausanne, 1999.  See also Pedone's home page.

Database State Machine is eager replication in the Schneider et al. sense of "state machine."  Some work on group multicast meeting "exactly" the requirements for DB concurrency control.   Most of this work appears in joint papers with Wiesmann and Schiper.  Seems like a nice piece of work.

[PC99] E. Pitoura and P. Chrysanthis.  Scalable Processing of Read-Only Transactions in Broadcast Push.  IEEE International Conference on Distributed Computing Systems, Austin, 1999.

[PGS98b]  F. Pedone, R. Guerraoui and A. Schiper.  Exploiting atomic broadcast in replicated databases.  Proceedings EuroPar 98.

A good description of using atomic broadcast in place of traditional atomic commitment protocol for improved performance.  The full version is in Pedone's thesis [P99].  

[PGS99]  F. Pedone, R. Guerraoui and A. Schiper.  The database state machine approach.  Technical Report SSC/1999/008, Ecole Polytechnique Federale de Lausanne, March 1999.

From [P99].

[PH+94] C. Pu, W. Hseush, Gail Kaiser, K. Wu and P. Yu.  Divergence Control for Distributed Database Systems.  Distributed and Parallel Databases, 1994.

[PL91] C. Pu and A. Leff.  Replica Control in Distributed systems: An Asynchronous Approach.  Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data.

[Pow96]  D. Powell, editor.  Group communications.  CACM 39:4, April 1996.

Special issue on group communications.  Not especially deep, but the sections by Schiper+Raynal (group communications -> transactions) and by F. Cristian are worthwhile.  Note it seems easier to exploit multicast for commit of a replicated transaction than for general distributed commit, and this paper seems not to address that issue. 

[PS00]  E. Pacitti and E. Simon.  Update propagation strategies to improve freshness in lazy master replicated databases.  INRIA Technical Report 3233, August 1997.  Also in VLDB Journal (2000) 8: 305-318.

Lazy master system concentrating on propagation latency ("freshness" of data) rather than throughput or scalability issues.  Of some interest, probably not worth presenting.

[PST+97] K. Petersen, M. Spreitzer, D. Terry, M. Theimer and A. Demers.  Flexible Update Propagation for Weakly Consistent Replication.  Proceedings of the 16th ACM Symposium on Operating Systems Principles, 1997.

[RGK95] M. Rabinovich, N. Gehani and A. Kononov.  Scalable Update Propagation in Epidemic Replicated Databases.  AT&T Bell Laboratories, 1997.

[RP94] K. Ramamritham and C. Pu.  A Formal Characterization of Epsilon Serializability.  IEEE Transactions on Knowledge and Data Engineering, 1994.

Formal definition of epsilon-serializability where update txns are required to be serializable, queries allowed to run with bounded inconsistency.

[RR97]  L. Rodrigues and M. Raynal.  Atomic broadcast in asynchronous crash-recovery distributed systems.  Technical Report TR 99-7, Departamento de Informatica, Universidade de Lisboa, Portugal, 1999.

[SAS+95] J. Sidell, P. Aoki, A. Sah, C. Staelin, M. Stonebraker and A. Yu.  Data Replication in Mariposa.  Berkeley EECS Technical Report, 1995.

[Sch97]  A. Schiper.  Early consensus in an asynchronous system with a weak failure detector.  Distributed Computing, 10(3), 1997.

[SNR+99] J. Shanmugasundaram, A. Nithrakashyap, K. Ramamritham and R. Sivashankaran.  Efficient Concurrency Control for Broadcast Environments.  SIGMOD 1999.

[TAR99] F. Torres-Rojas, M. Ahamad and M. Raynal.  Timed consistency for Shared Distributed Objects.  Proceedings 18th PODC, 1999.

[TDP+94] D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, and B. Welch.  Session Guarantees for Weakly Consistent Replicated Data.  Proceedings of the Third International Conference on Parallel and Distributed Information Systems, 1994.

[WPS99]  M. Wiesmann, F. Pedone, A. Schiper.  A Systematic Classification of Replicated Database Protocols based on Atomic Broadcast.

What the title says.  This paper reads as if it were very preliminary, even though the authors surely know a great deal about this stuff.

[WPS+99]  M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso.  Understanding Replication in Databases and Distributed Systems.

The topic of this course!  An interesting place to start, but I found it disappointing.

[WPS+00]  M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso.  Database replication techniques: a three parameter classification.  Proceedings of 19th IEEE Symposium on Reliable Distributed Systems (SRDS2000), October 2000.

Compare this classification with [WPS99].

[YV00] H. Yu and A. Vahdat.  Design and Evaluation of a Continuous Consistency Model for Replicated Services.  Proceedings 4th OSDI, Oct. 2000.

[YVb00] H. Yu and A. Vahdat.  Efficient Numerical error bounding for Replicated Network Services.  Technical Report, Duke University, 2000.