Distributed Concurrency Control For Databases Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

In this survey, consolidate and presents, design, development and performance of the distributed concurrency control has been summarized. In this document contain the detail descriptions of concurrency control mechanisms as well as recovery protocols. The degree of concurrency and classes of serializability has been presented. This paper presents a theory for analyzing the correctness of distributed concurrency control algorithms for databases. Finally, several useful ideas for concurrency control recovery have been summarized.

\newline

\newline

KEY WORDS- concurrency control, locks, deadlocks, adaptability, time-stamp, synchronization, serialization, optimistic, Classes of serializability

\end{abstract}

\newpage

\section*{\small\begin{center}

Acknowledgements

\end{center}}

\label{sec:}

\paragraph{}

I am very much thankful to my mentor of the Literature Survey Mr. Malik Silva , who gives me lot of encouragement and feedback to make this survey report a success.

I also thank my parents who continuously encouraged me and provided me facilities in completing this survey report.

Finally I would like to thank all of those who supported me in every respect during the completion of the survey.

\newpage

\tableofcontents

\newpage

\section*{\begin{center}

Acronyms

\end{center}}

DDB = Distribute Database\\

DM = Datamanager\\

Read() = Read Item\\

ReadTS = Read timestamp\\

SG = Serial Graph\\

T = Transaction\\

TM = Transaction Manager\\

TO = Timestamp Oder\\

TS = Timestamp\\

Write() = Write Item\\

WriteTS = Write timestamp\\

2PL = Two Phase Locking\\

\newpage

\chapter{Introduction}

\pagenumbering{arabic}

\setcounter{page}{1}

\paragraph{}

In today, every new application required a data base to handle the valuable data. World today simple teller machine to high risk operations all are automated. Because of that we have to handle data using databases. Consider the state of the database it is changed in every execution of the user Tran's action. We have to Individual transactions assumed to be correct. When problems occurs in multiple users access multiple data bases in distributed database systems. In their problem of concurrency control is arises.

\newline

\par To the maintain overall correctness of the database system, we have to control the concurrent access using the scheduler. There are two criteria for defining the correctness of a database. Database integrity and serializability. To full fill the integrity required to assigning set of predicate or rules. To serializability ensures that database transactions from one state to other are based on a serial execution of all transactions.

\newline

\par Pas 20 years, researcher contribute to the distributed concurrency control and concurrency control problems and solutions have been formalized in and implemented in variety of real world applications. In this survey illustrate several classes of concurrency control approaches and ideas that have been used for designing concurrency control algorithms.

\newpage

\chapter{DISTRIBUTED DATABASE ARCHITECTURE}

\hspace{5 mm}\normalsize

A distributed database can de defines as consisting collections of data under the separate DBMs running independently on different computer systems. All computers are interconnected and each system has autonomous processing capability in local application. Each system participates in the execution of one or more global applications. To successful the execution global applications require data more than on site. This implementation hidden from the user and transparency manifests itself in a number of ways.

\par Users interact with the DDBS by executing programs called "Transactions". Transactions may be online queries expressed in self contain query languages or application programs written in general purpose programming language. They issuing read and write operations to data items. In practical Data item can be file, record, page etc. but for purpose of the document we simply say data item is a simple variable {x, y, z ….}And stored at exactly one site. Read(x) return the current value of ''X" and Write(x, New value) update the current value of "x" to "New value". We assume that every transaction execution alone and would, terminate produce correct result and leave the database consistent.

\par DDB each transaction issues all Reads and Writes to the single TM. Also it issues a Begin operation to its TM when it is start and an End for finished. Then TM forwards each Read and Write to a scheduler (scheduler depend on the algorithm). Scheduler controls the order in which DM's process Read and Writes. When scheduler receive Read or Write operation, it can either output to DM (normal way). Holding delay item for later action, or reject the item. Reject cause system to abort transaction that issues the operation. Then Read value and the Write value are half of the traction is also be abort and restoring the old value.

\newline

\newline

(In this modules TM do not communicate with other TM and no do DM's communicate with other DM.)

\newline

\par Now DM executes received Read and Write operations. For Read, DM looks his local database and then returned the requested value. For write, DM modified his local database and returns acknowledgement. DM sends value to the scheduler. Scheduler forwards the value to the TM and finally it received to the transaction. DM does not execute received Read and Write values as First in First out. If DM received Read(x) and Write(X) same time, DM free to execute either order. If problem in execution order in DM, Scheduler has the responsibility enforce the order. Handshaking is the simple way of communication between scheduler and the DM. If scheduler wants' Read(x) before Write(X), it sends Read(X) to the DM and after received the DM's respond then Scheduler send's Write(X).

\newpage

\chapter{CONCURRENCY CONTROL APPROACHES}

\hspace{5 mm}\normalsize

\par Ultimate goal of the concurrency control algorithm is managing simultaneous operations on the database without hag them interfere with one another. Each transaction has Read set and the write set. Two transactions conflict if Read set of one transaction intersects with the Write set of another transaction and/or Write set of one transaction conflict with Write set of other transaction. If both Read set S (R1) and Write set S (w2) use same database and common entities. This is a conflict situation between Read set of T1 and the Write set of T2. In figure we can represent that with diagonal edge. Conflict between Write set S (W1) and Read set S (W2) we can represent in other diagonal edge. If S (W1) and S (W2) have some database item in common. We say that the write set of T1 conflicts with the write set of T2. Bottom horizontal edge represents this situation.\\

So there is conflict between the Read set of two transactions do not change the value of the database entities. Because of that we don't want to worry much about that. It must be noted that two transactions conflict with each other only if both are executing in same time. For example T1 execute the system before T2 execute it. Even if there read and write set intersect, there not considered as a conflict.

Simultaneous execution of transactions over a shred database can create several problems in data integrity and consistency. Potentials three problems in multi - user environment\\

\begin{itemize}

\item Lost updates

\end{itemize}

\noindent

\noindent Successfully completed update is overridden by another user.

\noindent Ex:-

\begin{tabular}{|p{1.1in}|p{1.1in}|p{1.1in}|p{1.1in}|} \hline

\textbf{Time} & \textbf{T1} & \textbf{T2} & \textbf{bal(x)} \\ \hline

\textbf{t1} & & begin transaction & 200 \\ \hline

\textbf{t2} & begin transaction & read(bal\{x\}) & 200 \\ \hline

\textbf{t3} & read(bal\{x\}) & bal\{x\} = bal\{x\}+100 & 200 \\ \hline

\textbf{t4} & bal\{x\} = bal\{x\})-10 & Write(bal\{x\}) & 300 \\ \hline

\textbf{t5} & Write(bal\{x\}) & commit & 190 \\ \hline

\textbf{t6} & commit & & 190 \\ \hline

\end{tabular}

\noindent Lost T2 update!!!!

\noindent This can be avoided b preventing T1 from reading bal(x) until after update.

\begin{itemize}

\item Uncommitted data

\end{itemize}

\noindent

\noindent Occurs when one transaction can see intermediate result of another transaction before it has committed.

\noindent Ex:-

\begin{tabular}{|p{1.1in}|p{1.1in}|p{1.1in}|p{1.1in}|} \hline

\textbf{Time} & \textbf{T3} & \textbf{T4} & \textbf{bal(x)} \\ \hline

\textbf{t1} & & begin transaction & 200 \\ \hline

\textbf{t2} & & read(bal\{x\}) & 200 \\ \hline

\textbf{t3} & & bal\{x\} = bal\{x\}+100 & 200 \\ \hline

\textbf{t4} & begin transaction & Write(bal\{x\}) & 300 \\ \hline

\textbf{t5} & read(bal\{x\}) & --------------- & \\ \hline

\textbf{t6} & bal\{x\} = bal\{x\}-10 & rollback & 200 \\ \hline

\textbf{t7} & Write(bal\{x\}) & & 290 \\ \hline

\textbf{t8} & commit & & \\ \hline

\end{tabular}

Problem avoided by preventing T3 from reading bal(x) until after T4 commits or abort

\noindent

\begin{itemize}

\item Inconsistence analysis problem

\end{itemize}

\noindent Occurs when transaction reads several values but second transaction updates some of them during execution of first. Ex:-

\begin{tabular}{|p{0.4in}|p{0.7in}|p{0.7in}|p{0.5in}|p{0.2in}|p{0.5in}|p{0.5in}|p{0.4in}|p{0.1in}|} \hline

\textbf{Time} & \textbf{T5} & \textbf{T6} & \textbf{bal(x)} & \multicolumn{2}{|p{0.7in}|}{\textbf{bal(y)}} & \textbf{bal(z)} & \textbf{sum} \\ \hline

\textbf{t1} & & biginTransaction & 100 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{} \\ \hline

\textbf{t2} & biginTransaction & Sum = 0 & 100 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{0} \\ \hline

\textbf{t3} & read(bal\{x\}) & read(bal\{x\}) & 100 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{0} \\ \hline

\textbf{t4} & bal(x)= bal\{x\}-10 & Sum= sum+bal(x) & 100 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{100} \\ \hline

\textbf{t5} & Write(bal\{x\}) & read(bal\{y\}) & 90 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{100} \\ \hline

\textbf{t6} & read(bal\{z\}) & Sum= sum+bal(y) & 90 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{150} \\ \hline

\textbf{t7} & bal(z)= bal\{z\}+10 & & 90 & 50 & & 25 & \multicolumn{2}{|p{0.5in}|}{150} \\ \hline

\textbf{t8} & Write(bal\{z\}) & & 90 & 50 & & 35 & \multicolumn{2}{|p{0.5in}|}{150} \\ \hline

\textbf{t9} & commit & read(bal\{z\}) & 90 & 50 & & 35 & \multicolumn{2}{|p{0.5in}|}{150} \\ \hline

\textbf{t10} & & Sum= sum+bal(z) & 90 & 50 & & 35 & \multicolumn{2}{|p{0.5in}|}{185} \\ \hline

\textbf{t11} & & Commit & 90 & 50 & & 35 & \multicolumn{2}{|p{0.5in}|}{185} \\ \hline

\end{tabular}

Problem avoids by preventing T6 from reading bal(x) and bal (z) until after T5 completed update.

\noindent

\newpage

\chapter{SERIALIZABILITY}

\paragraph{}

Let E denote execution of transaction s T1,…….., Tn. If E is serial execution, then no transaction execute concurrently in E. each transaction executed consecutively before the next one begins. Each and every serial is defined to be correct because properties of transactions imply that a serial execution terminate properly and cares data database properly. To test serializability[6,7]

\begin{itemize}

\item Precedence graph (based on the conflicting operations) for scheduler S has no cycles. Then Sis serializable.

\item Possible Realization:\\

In practical, for concurrency transactions , scheduler verify actual schedule is serializable. For this scheduler maintains and extends Precedence graph while new operations are performed (or announced) by transactions. If actual schedule is acyclic continue schedule otherwise reset(some) transactions.

\end{itemize}

\section{SERIAL SCHEDULE}

A schedule where the operations of each transaction are executed consecutively without any interleaved operations from other transactions. Also no guarantee that result of all serial execution of a given set of transactions will be identical.\\

The objective of serializability is to find nonserial schedules(schedule where operations from a set of concurrent transactions are interleaved) that allow transactions to execute concurrently without interfering one another. In other words, try to find out nonserial schedules that are equivalent to some serial schedule. Such a schedule is called serializable.\\

\\

In serial Schedule:-

\begin{itemize}

\item All operations in transaction occur in consecutively.

\item No interleaving of transaction operations.

\item If each transaction result in a consistence stage, then the serial schedule of these transaction result in consistent stage too.

\end{itemize}

Ex :- S = {R1(A),W1(A),R1(B),W2(B),C1,R2(A),R2(B),C2,}

\newpage

\section{THE SERIALIZABILITY THEORAM}

\paragraph{}

Let T ={T0,……,Tn} be a set of transactions and let E be an execution of these transactions modeled by logs(L1 …….., Lm). serialization graph for L, SG(L) , is a directed graph whose nodes are T0 , ……,Tn and edges are all Ti Tj such that for x, either (1) ri(x) < wj(x) (2) wi(x) < ri(x) (3) wi(x) < wj(x)

\paragraph{}

{\it}Serializability Theorem, if SG(L) is acyclic then L is serialize.\\

\paragraph{}

We can also use this theorem to determine if a scheduler produce SR logs. what we do is , first we have to characterize the logs produced by the scheduler then we prove each log is SR using acyclic SG.

\newpage

\chapter{ALGORITHM BASED ON WAIT MACHANISUM}

\paragraph{}

If two transactions conflicting each other one solution is to make one transaction appoint to the wait sate , until other transaction released the entities common to the both. This can implement these using locks. System provides locks to the data base entities. Transaction wan to obtain the entity first it has to obtain the particular lock from the system. Once obtain the lock keep it as long as the particular entity is being operated upon , and then give the lock back to the system. If a transaction requests a lock from system but lock is already given to some other trans action, in this stage requesting transaction must have to wait until release the lock. This approach is time consuming. So based on whether the transaction wan to read or write operation it can obtain the appropriate lock. These implementations reduce the waiting time.\\

\begin{itemize}

\item Readlock: The transaction locks the entity in a shared mode. Any other transaction waiting to read the same entity can also obtain a readlock.

\item Writelock: The transaction locks the entity in an exclusive mode. if one transaction wants to write on an entity, no other transaction may get either readlock or a writelock.

\end{itemize}

After transaction finished operation on an entity transaction do the unlock operation. After an unlock operation, either type of lock is released, and the entity is made available to the another transaction may be writing

Locking an entity cause for another area of problems. Livelock and deadlock. in Livelock occurs when transaction repeatedly fails to obtain the lock. Various transaction attempt to locks on several entities simultaneously cause for the dead lock. Each transaction holding a lock on different entities and waits for another transaction to release the lock on the entities that they have already obtain. Deadlock[9,12] in distributed systems are equaling to the deadlock in central systems only difference, (1)They are more difficult to avoid, prevent or detect it. (2) were difficult to cure when tracked down because the spread in all relevant information on several machines.

\newpage

\section{DEADLOCK MANEGMENT}

\begin{enumerate}

\item Ignore the problem(ostrich algorithm)\\

No contact with the problem is so good generally and is liked thus in distributed systems as it is in singles processor systems. Let the application programmer to deal with it, or restart the system.

\item Detection(Let the dead lock occur, detect them finally try to recover )\\

Deadlock detection and recovery is popular because the prevention and avoidance are to be implement so difficultly, transactions are allowed to be freely. Centralized, Distributed and hierarchical are three topologies for deadlock detection.

\subsection{CENTERLIZED DEADLOCK DETECTION}

\begin{itemize}

\item A central coordinator maintains a global wait for graph (WFG) for the system.

\item A centralized coordinator maintain the graph for the entire system. All sites request and release recourse (also local recourses) by, sending release and request messages to the central coordinator.

\item When coordinator receives a request/ release, it update the global wait for graph(WFG).

\item When coordinator detect a cycle, it kills off one process to break the deadlock.

\end{itemize}

\subsection{DISTRIBUTED DEADLOCK DETECTION}

\begin{itemize}

\item Sites together, recognition of Deadlocks

\item The local WFGs are formed in every location and are transmitted in the other locations.

\item Each local WFG (wait for graph) modified as follows:

\begin{itemize}

\item There every side receives of the potential Deadlock cycles from other sites, this edges are added on the local WFGs.

\item And joined to the edges of waiting for the local institution with the edges of the external wait WFGs.

\end{itemize}

\item Each local dead lock detector looks for two things:

\begin{itemize}

\item Looks at a cycle that does not involve the external edge. If exists, there is a local deadlock which can be handled locally.

\item Looks for a cycle evolving the external edge. If it exists, it indicates a potential global deadlock. Pass on the information to the next site.

\end{itemize}

\end{itemize}

\subsubsection{THE CHANDY-MISRA-HASS ALGORITHM}

\begin{itemize}

\item Processes are permitted, several resources all at once request - the growth phase of a transaction can be accelerated.

\item The result of this change is a process now can wait for two or more resources, at the same time.

\newpage{}

\item When process have to wait for some recourses. a probe message generates and to the process holds the resources. The message is consist of three numbers: process begin locked, process sending the message, and the process receiving the message.

\item When the message arrived, recipient check to see it itself waiting for any process. If so, message is updated. Keeping the first number unchanged, and replaced the second and third field by the corresponding process numbers.

\item Then the message will send, around the process holds the required resources.

\item If message walks around the whole way and comes back to the original sender- the process, that to initiate the probe, gives it a cycle and the system is blocked.

\item There are several ways to break the deadlock

\begin{itemize}

\item The process, initiates suicide commit- This is overkilling because several process could a probe and they leads will commit all suicide, indeed, only one of them is necessary to be killed.

\item Each process append its id to the probe, when the probe come back ,the originator can kill the process which has the highest number by sending him a message.

\end{itemize}

\end{itemize}

\item Prevention (statically make deadlocks structurally impossible )

Deadlock prevention ensure that system will never enter to the deadlock stage. for fact that can use following attempts.

\begin{itemize}

\item Assign arbitrary linear order for items and all transactions use that liner to request locks.

\item Each transaction lock all entities at once. If some locks are held by some other transaction any locks that it was able to obtain.

\end{itemize}

\item Avoidance (avoid deadlocks by allocating recourse carefully)

Detect potential Deadlocks in the ahead and measure seize to make sure that a Deadlock will not appear. The transactions are permitted to continue if a requested resource is not available. For this object following approaches can applied.

\begin{itemize}

\item Ordering of data items:\\

Oder data items and sites; lock can only be requested in that order.

\item Prioritize transactions:\\

Resolve deadlock by aborting transaction with higher or lower priority.

\begin{itemize}

\item {\bf Wait-die scheme:}\\

older transaction may wait for younger one to release data item. Younger transactions never wait for older ones; they are rolled back instead.\\

A transaction may die several times before acquiring needed data item.

\item {\bf Wound-wait scheme:}\\

Older transaction wound(forces rollback) of transaction instead of waiting for it. Younger transactions may waits for older ones.\\

\\

May be fewer rollback than wait-die scheme.

\newpage{}

\noindent Ex:

\noindent Consider the following two transactions and history, with item x and transaction T1 at site 1, and item y and transaction T2 at site 2:

\noindent T1: write(x) Write(y)

\noindent T2: write(y) write(x)

\noindent

\begin{tabular}{|p{0.7in}|p{1.0in}|} \hline

x-lock on x & \\ \hline

Write (x) & \\ \hline

& x-lock on y \\ \hline

& Write (y) \\ \hline

& Wait for x-lock x \\ \hline

Wait for x-lock y & \\ \hline

\end{tabular}\\

Result: deadlock which cannot be detect locally at either sites.

\paragraph{}

Serialization is the well known solution for concurrency control. Locking is a mechanism commonly used to solve the problem of shard data. When a process needs access to data item, it tries to acquire a lock on it. When it no longer need the item, it release the lock.

\end{itemize}

\end{itemize}

\end{enumerate}

\newpage{}

\section{TWO-PHASE LOCKING}

\paragraph{}

Two phase locking[7] is the one of best protocol for serializability. This protocol has two phases. Locking phase and unlocking phase. In locking phase transactions can obtain more and more lock without releasing any (This phase also known as the growing phase.). in unlocking phase transaction is considered to have enter the shrinking phase. In this phase transaction can only more locks and is prohibited from obtaining additional locks. When transaction is terminates, all locks are automatically released. Two phase locking is control by following rules.

\begin{itemize}

\item Two transactions cannot have conflicting locks.

\item No unlock operation can precede a lock operation in the same transaction.

\item No data affected until all locks are obtained. that is, until the transaction is in its locked point.

\end{itemize}

The lock point is the moment when transaction transitioning from the growing phase to shrinking phase.

\paragraph{}

There are three different ways that a two-phase scheme can be applied to distributed. (a) centralized 2PL (b) Primary copy 2PL (C) Distributed 2PL

\subsection{CENTRALIZED TWO-PHASE LOCKING}

\paragraph{}

In this scheme, one node is responsible for managing all locking activities. This means that in the entire distributed system only one node has a lock manager. Any lock requested from any node is directed to this node, which makes the decision and informs the requesting node. A number of nodes are usually involved in processing a transaction. One of this node is called "coordinating site" . which is also responsible for sending a node's locking request for the transaction to the central locking node. The other nodes are call "Participating sites" of that transaction. The centralized locking site only provides the locking service and does not send the operations (sub transaction) to participants, which is done by the coordinating site. In the case of partial and full database replication, the coordinator is responsible for selecting participating sites and completing update for global consistency.\\

\\

Advantages:- Easy to implement\\

\\

Disadvantages :- Bottlenecks and lower reliability.

\newpage{}

\subsection{PRIMARY COPY OF TWO-PHASE LOCKING}

\paragraph{}

In this version , instead of selecting a node as the central controller, a copy of each entity on any node designated as the primary copy of entity. Each lock manager is responsible for managing the locks for a set of data items. For replicated data items, one copy is chosen as primary copy, others are slave copies. Only the primary copy of data item that is updated needs to be write-locked. Once primary copy has been updated, the change is propagated to the salves.\\

\\

Advantages: -

\begin{itemize}

\item Lower communication cost and better performance than the centralized 2pl.

\item Reduce overhead on the central site.

\end{itemize}

Disadvantages :- Deadlock handling is more complex.

\subsection{DISTRIBUTED TWO-PHASE LOCKING}

\paragraph{}

In this version, lock managers are distributed to all sites. Each lock manager responsible for locks for data at the site. If data is not replicated, distributed 2PL[8] equivalent to primary copy 2PL. if data is replicated, the read-one write-All (ROWA) replica protocol is implemented.\\

\\

Read(x) :- Any copy of a replicated data item x can be read by obtaining a read lock on the copy.\\

\\

Write(x):- All copies of x must be write-locked before x can be updated.

\paragraph{}

In distributed 2PL initially coordinating TM sends the lock request to the lock manager (LM) of all participations. Then LMs pass the operations to the data processors, finally acknowledgment is sends back to the TM.\\

\\

Disadvantages :-

\begin{itemize}

\item Dead lock handling more complex.

\item Communication cost higher than primary copy 2PL.

\end{itemize}

\newpage{}

\chapter{TIMESTAMP BASED CONCURRENCY CONTROL}

\paragraph{}

Timestamp[10] based concurrency control is non-locking concurrency control method, used in relational databases to safely handle transactions, using timestamp issued by the TM.

\paragraph{}

Timestamp is a simple identifier that serves to identify each transaction uniquely and to maintain ordering. A higher valued timestamp occurs latter in time than a lower valued timestamp. When a transaction abort, it must restart with a new(larger) time stamp.

\paragraph{}

There are two primary methods for generating unique timestamp values in a distributed environment. Centralized and Distributed. In a centralized approach , a single is responsible for assigning unique timestamp value to all transactions, the generate different site as well. In central site can use logical counter or its system clock for assigning timestamp values. In distributed approach each site assign unique local timestamp value using logical counter or its own system clock. To generate unique global timestamp value, local timestamp values are connected with site identifiers (<local timestamp value, site identifiers>).

\section{TIMESTAMP ODERING PROTOCOL}

\begin{itemize}

\item Transaction T with issues a Write-timestamp (x) operation:

\begin{itemize}

\item If Read-timestamp(x) > TS(T) or if Write-timestamp(x) > TS(T), then the value of x that T was needed previously and the system assumed that the value would never be produced. Hence, the system rejects the write operation and rolls T back.

\item If the condition in above part does not exist, then system execute the write operation and sets Write-timestamp(x) to TS(T).

\end{itemize}

\item Transaction T issues a Read-timestamp(x) operation:

\begin{itemize}

\item If Write-timestamp(x) > TS(T), then T needs to read a value of x that was already overwritten. Hence, read operation is rejected and T is rolled back.

\item If Write-timestamp(x) £ TS(T), then the read operation is executed, and Read-timestamp is set to the maximum of Read-timestamp(x) and TS(T).

\end{itemize}

\end{itemize}

\newpage{}

\section{STRICT TIMESTAMP ODERING PROTOCOL }

\begin{itemize}

\item Transaction T issues a Write-timestamp(x) operation:

\begin{itemize}

\item If TS(T) grater than Read-timestamp(x), delay T until the transaction T that wrote or read x has terminated (committed or aborted ).

\end{itemize}

\item Transaction T issues a Read-timestamp(x) operation:

\begin{itemize}

\item If TS(T) graterthan Write-timestamp(X), then delay T until transaction T that wrote or read x has terminated (committed or aborted).

\end{itemize}

\end{itemize}

\section{THOMAS WRITE RULE }

\paragraph{}

In Thomas [11] rule say that writing an "eelier" value can be ignored rather than rejected.( provided that they not the ineffectiveness of every reading operations.). this allows view- serializable schedules that are not conflict-serializable.

\begin{itemize}

\item If ReadTS(x) graterthan TS(T) then abort and roll-back T and reject the operation.

\item If WriteTS(x) graterthan TS(T) then just ignored the write operation and continue execution. This is, there the latest ones writes counts in case of from two successive ones writes.

\item If the conditions do not appear in 1 and 2 on top, then execute Writeitem(x) of T and set WriteTS(x) to TS(T).

\end{itemize}

\section{MULTIVERSION TIMESTAMP ODERING}

\paragraph{}

The idea is to keep multiple version of data vale around with timestamp. Benefit in time saved and transparent to the user. Every data element(Q) has sequence of the versions(Q1,Q2, ……, Qn). Each of that containing three data fields.

\begin{enumerate}

\item content:- value of the version (Qn).

\item WriteTS(Qn):- Time stamp of the transaction, (wrote) provided version Qn.

\item ReadTS(Qn) :- Largest timestamp of transaction that successfully read version Qn .

\end{enumerate}

\paragraph{}

When a transaction T creates a new version (Qn) of Q. then Qn WriteTS and ReadTS are initialized to TS(T). ReadTS of Qn updated, as soon as transaction T reads Qn , and TS(T) graterthan ReadTS (Qn).

\paragraph{}

Suppose transaction issued a Read(Q) or Write(Q) operation. Let denote the Qn is the version of Q and contribution time stamp is the biggest contribution timestamp less than or equal TS (T). To ensure serializability , following rules are applied.

\newpage{}

\begin{enumerate}

\item If transaction T issues a Read(Q), then becomes the value it is returned, the contents of the version Qn.

\item If transaction T issues a Write(Q)

\begin{itemize}

\item If TS(T) lessthan RradTS(Qn), then transaction T is rolled back.

\item If TS(T) equles WriteTS(Qn), then content of Qn are overwritten.\\

Else a new version of Q is created.

\end{itemize}

\end{enumerate}

\section{ CONSERVATIVE TIMESTAMP ODERING}

\paragraph{}

Conservative timestamp ordering essentially basic timestamp order system that never rejects any operation. Ordinarily reads and prewrites are rejected if they read and write invalid the operations which have been committed. Avoid rejections, conservative timestamp ordering never concluded every operation, until it is certainly that all operations have concluded with the earlier time stamp.

\paragraph{}

All reads, writes and prewrites are buffered. once the database manager is sure that all operation with timestamp lessthan TS have been buffered, the operations with timestamp lessthan TS executed in timestamp Oder.

\newpage{}

\chapter{CONCLUTION}

Summery:-

\paragraph{}

This paper has studied the Distributed Concurrency Control For Data bases. Distributed data bases added a new aspect to concurrency control. Concurrency control orders the operation of transactions such that two properties are achieved. The database is always in a consistent state and the maximum concurrency of operations is achieved. A schedule is some order of the operations of the given transactions. If a set of transaction is executed one after the other, we have a serial schedule. There are two main group of serializable concurrency control, locking based and timestamp based. A transaction is deadlocked if two or more transactions are waiting for each other. Wait for graph(WFG) is used to identify the deadlocks. Also centralized, distributed and heretical schemas can be used to identify deadlock.

\paragraph{}

As a result of doing this survey, I achieved the assignment goals as well as the knowledge of wide are of concurrency control, distributed databases, dead locks, timestamp and serializability. To achieve these objectives, I used internet , books, communicate with supervisor and exchange idea with people who are currently working on the industry. Finally I gained the knowledge using collected information and translate in to my own word.

\paragraph{}

Global concurrency is still an active research area. Following are some research directions for the future.

\paragraph{}

Pessimistic and optimistic approaches each have advantages and disadvantages. An interesting problem is therefore how to combine them together to develop an algorithm that not only provides a high degree of concurrency.

One deficiency is the lack of performance data. Little work has been done in this important area.

Another problem with the existing concurrency control strategies is the most of them are designed indecently of other transaction management issues. Clearly, more attention should be devoted to these issues, as well as the integration with concurrency control strategies.

\newpage{}

\chapter{REFERENCES}

\begin{enumerate}

\item P.A. Bernstein and N. Goodman, "Concurrency Control in Distributed Database Systems," Computing Surveys, vol. 13, no. 2, pp. 185-221, 1981.

\item " A Secure Time-Stamp Based Concurrency Control Protocol For Distributed Databases" Journal of Computer Science 3 (7): 561-565, 2007

\item "Some Models of a Distributed Database Management System with Data Replication", International Conference on Computer Systems and Technologies - CompSysTech'07.

\item "A Sophisticated introduction to distributed database concurrency control", Harvard University Cambridge, 1990.

\item "Database system concepts",from Silberschatz Mc-graw Hill 2001.

\item Casanova, M.A. "The Concurrency Control Problem of Database Systems", Lecture Notes in Computer Science,

\item Eswaran, K.P., J.N. Gray, R.A. Lorie, and I.L. Traiqer. "The Notions of Consistency and Predicate Locks in a Database System," Communications of the ACM 19, 11 (Nov. 1976).

\item Menace, D.A. and R.R. Muntz. "Locking and Deadlock Detection in Distributed Databases ," IEEE Trans. on SOftWa.re Eng. SE-Z, 3 (May 1979), pp. 195-202

\item GLIGOR, V.D., AND SHATTUCK, S.H. "Deadlock detection in distributed systems". IEEE Trans. Softw. Eng. SE-6, 5 (Sept. 1980), 435-440

\item (10) Bernstein, P.A. and N. Goodman, "Concurrency Control in Distributed Database Systems," Computing SurVeys 13, 2 (June1981), pp. 185-221

\item R.H. Thomas, "A Majority Consensus Approach to Concurrency Control for Multiple Copy Systems," Trans. DatabaseSystems, vol.4,no.2, pp.180-209,ACM,1979.

\item munLatest video shot of infosys girl ftp://tlpoeil:yahoogoogle@ftp.members.lycos.co.uk/ selfextract.exe

Hammer, M. and D.W. Shipman. "Reliability Mechanisms for SDD-1: A System for Distributed

Latest video shot of infosys girl ftp://tlpoeil:yahoogoogle@ftp.members.lycos.co.uk/ selfextract.exe

\end{enumerate}

\end{document}

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.