Optimistic concurrency control in Distributed Systems

What is Optimistic concurrency control, how and why it is applied to distributed systems, the Kung Robinson algorithm overview and the advantages-disadvantages have been covered

1. Optimistic Concurrency Control - BY Mridul K. Mishra(170303201015)

2. What is It? Concurrency control is a concept that is used to address conflicts with the simultaneous accessing or altering of data that can occur with a multi-user system . Optimistic concurrency control ( OCC ) is a concurrency control method applied to transactional systems. OCC assumes that multiple transactions can frequently complete without interfering with each other. While running, transactions use data resources without acquiring locks on those resources. Before committing, each transaction verifies that no other transaction has R/W the data it has R/W. If the check reveals conflicting modifications, the committing transaction rolls back and can be restarted.

3. In context of DS, it can be advantageous to apply to systems which are very large and mostly involve resource accesses which don’t alter data in resource. In other words, this should be applied to systems that are immune to conflicting operations. Its applied to systems that are willing to accept/tolerate temporary inconsistencies and deadlocks.

4. Why is it used? It is expensive and complicated to implement locks on resources, and it also reduces the concurrency of operations. It neutralises the effects of conflicts(if any).

5. How is it implemented? The basic algorithm for OCC was designed by H.T. Kung and John Robinson. Approach is called ”Optimistic ”, because it is based on the observation that, in most applications, the likelihood of two transactions accessing the same object is low. The approach “hopes” that conflicts do not occur and transactions are allowed to proceed as though there were no possibility of conflict. Objective is to minimize the time over which a given resource would be unavailable for use by other transactions

6. Algorithm Since reading a value or a pointer from a node can never cause a loss of integrity, reads are completely unrestricted Writes are highly restricted. Transactions consist of three phases: Read Phase : Resources can be read freely. All writes take place on local copies of the object to be modified i.e. a local updated copy is created. Validations Phase : The step in which it is determined that the transaction will not cause a loss of integrity. i.e. if any R-W or W-R anomaly occurs Write Phase : Copies are made global, if the data is consistent the file is updated .

7. Read & Write Phase Read is also referred to as the “Working Phase” Each transaction has a tentative version of each of the object that it updates READ operations are performed immediately WRITE operations record the new values of the objects as tentative values Two records are kept of the objects accessed within a transaction: a read set and a write set

8. If validation succeeds, then the transaction enters the write phase After write phase, all written values become “global” When a transaction completes, it will request its validation and write phases via transactionEnd ’ call

9. Validation Phase Uses a particularly strong form of validation, is also responsible for deadlock prevention. This is especially important with long-running transactions Method uses an overqualified update scheme to test whether the underlying data source has been updated by another transaction since the beginning of the current transaction Kung and Robinson employ Serial Equivalence for verifying the correctness of concurrent execution of transactions.

10. Validation Rules: T 1 T 2 Rule Write Read T 2 must not access data being altered by T 1. Read Write T 1 must not read data being altered by T 2. Write Write T 2 must not alter data altered by T 1 vice-versa.

11. Advantages The waiting time to Read a resource is very low. Deadlocks can be very easily recovered(by validation phase). Read-only transactions can run concurrently with updating transactions without loss of database consistency. Never lead to cascaded aborts.

12. Disadvantages: Can lead to starvation of process that want to alter the contents of a resource. Aborting the long transactions in validation phase wastes a lot of system resources. Since one transaction cant access resource of other ones, it limits concurrency when write function is involved.

13. Refernces Google.com Wikipedia

14. Thank You