Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. EPFL thesis
  4. Causal approaches to concurrency control in distributed and replicated database systems
 
doctoral thesis

Causal approaches to concurrency control in distributed and replicated database systems

Sandoz, Alain
1992

The dissertation concerns the study of concurrency control in distributed and replicated database systems under conflict preserving constraints. The development focuses on the introduction and understanding of the casual relationship in conflict preserving serializable (cpsr) database logs. The presentation of results and contributions is organized in four steps. After a brief overview of the serialization problem for unique copy and replicated databases, a new protocol is presented for pessimistic concurrency control of a replicated database. The protocol is a generalization of most traditional schemes based on mutual exclusion between conflicting logical database operations, which allows some old reads in the database. In particular, the partitioned state of the underlying network is transparent to the scheduler. The concepts of adaptation and recovery of the concurrency control mechanism after partition do not appear in the protocol. Rather, the causal relationship is recognized as a driving concept behind one-copy serializability under conflict preserving constraints. In the second step, the preceding remark is developed into a new causal model for cpsr in unique copy databases. The causal model formally introduces the causal relationship and the notion of time in the database, independently from any mechanism in the database management system which is not related to the serialization problem. The model is a tool which enables both the understanding of traditional concurrency control mechanisms and their limitations due to dependencies on computer system related constraints, and the construction of new mechanisms. The latter aspect is developed by exhibiting a new subclass of conflict preserving serializable logs, the BPS class. A distributed non-blocking protocol for this class is presented along with a brief study of the amount of concurrency tolerated by the BPS policy. Finally, the causal model is extended to replicated and multiple version databases. In this manner a unique framework is proposed for the study of concurrency control in databases with heterogeneous representations of items. Replication and multiple versions are transparent in this model, which leads to develop a new concept: the scheduler service for concurrency control in general databases. The scheduler service is a database service whose unique functionality is to decide whether transactions are serializable or not. In particular, it is independent of access policies enforced at the transaction and data manager levels. This leads to develop non-blocking pessimistic replicated database schedulers which allow reading by accessing a unique copy, and which can tolerate some old reads. Several examples are presented and an implementation is described for a nonblocking strict-2PL replicated database scheduler. Important implications on the architecture of the database management system are also developed.

  • Files
  • Details
  • Metrics
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés