Optimistic Cocurrency Conrtol - Sacrifice Protocol

Real-time optimistic concurrency control protocols, OCC-Sacrifice, How does OCC-Sacrifice work?

Optimistic Concurrency Control – Sacrifice

This method includes priority mechanism in OCC-BC. This change makes this protocol as one of the real-time optimistic algorithms. OCC-Sacrifice works as follows;

All the transactions can work on any data items freely as in the case of OCC-BC.

• When a transaction reaches its validation stage, it checks for the conflicts in all the ongoing concurrent transactions.

• If there exists any conflicts, then check for the priority of the conflicting transactions.

• If one or more of those transactions’ priorities are higher than the validating transaction, then validating transaction gets restarted, i.e., it sacrificed for the higher priority transactions to meet their deadlines.

Pseudocode for OCC-Sacrifice

If Conflicting Higher Priority transactions in conflict set then

Restart the validating transaction;

Else

Restart transactions in conflict set;

Commit the validating transaction;

Example 1:

Consider three transactions T1, T2, and T3 that are working concurrently on some data items. Assume that the following are the complete information about these transactions;

• T1 and T2 are working on data item X, and T3 is working on data item Y.

• T1 is working with higher priority, T2 with lower priority and T3 with any priority.

• T2 has reached the end of the transaction. That means, T2 is the validating transaction according to the OCC-Sacrifice algorithm.

Now OCC-Sacrifice works as follows;

• T2 checks for a conflict with any other ongoing concurrent transactions for conflicts.

• T3 will not conflict with T2 because T3 is working on different data items. T1 will conflict with T2 as both are working on same data item X.

• The protocol now has to check for the priority of the conflicting transaction (T1). The priority of T1 is higher than that of T2 (Given, P(T1) > P(T2)). Now, according to the protocol, T2 (validating transaction) restarts by sacrificing the work done so far. This will lead T1 to reach its deadline without delay.

Example 2:

Consider three transactions T1, T2, and T3 that are working concurrently on some data items. Assume that the following are the complete information about these transactions;

• T1 and T2 are working on data item X, and T3 is working on data item Y.

• T2 is working with higher priority, T1 with lower priority and T3 with any priority.

• T2 has reached the end of the transaction. That means, T2 is the validating transaction according to the OCC-Sacrifice algorithm.

Now OCC-Sacrifice works as follows;

• T2 checks for a conflict with any other ongoing concurrent transactions for conflicts.

• T3 will not conflict with T2 because T3 is working on different data items. T1 will conflict with T2 as both are working on same data item X.

• The protocol now has to check for the priority of the conflicting transaction (T1). The priority of T2 is higher than that of T1 (Given, P(T2) > P(T1)). Now, according to the protocol, T2 (validating transaction) commits and T1 restarts by sacrificing the work done so far. This will lead T2 to reach its deadline without delay.

Disadvantage:

Wasted sacrifices are possible. That is, a transaction is sacrificed due to lower priority but later the higher priority transaction discarded due to some other reasons. This is similar to that of 2PL-HP protocol.

********

Go back to Optimistic Concurrency Control protocol page

Go to REAL TIME DATABASE Home page

Temporal consistency in real time database solved exercise

Temporal consistency, real-time database, solved exercise, find whether the given relative consistency set are temporally consistent or not? absolute consistency, relative consistency

Exercise:

To check whether the given temporal data are consistent or not.

Let us consider a boiler which is equipped with sensors to monitor its pressure and temperature at any point in time. Assume that the temperature reading at time 2000 msec is 100^o C and this reading is valid for only 30 msec. Also assume that the pressure reading at time 2010 msec is 50 bar and this reading is valid for only 20 msec. If these data are relatively valid for 20 msec and the current time is 2020 msec, temperature and pressure are temporally consistent?

Solution:

For a data item to be temporally consistent, it has to be absolutely consistent and also relatively consistent with the other related data items.

Given,

• Relative consistency set R = {Temperature, Pressure}
• Temperature reading validity duration, Temperature_avi = 30 msec
• Temperature = (value, avi, timestamp) = (100^oC, 30 msec, 2000 msec)
• Pressure reading validity duration, Pressure_avi = 20 msec
• Pressure = (value, avi, timestamp) = (50 bar, 20 msec, 2010 msec)
• Relative validity interval R_rvi = 20 msec
• Current time = 2020 msec

A data item is absolutely consistent if |current_time – d_timestamp| <= avi

A set of data items d and d’ are relatively consistent if |d_timestamp – d’_timestamp| <=R_rvi

|current_time – Temperature_timestamp| = |2020 – 2000| = 20 msec which is less than or equal to Temperature_avi 30 msec. Hence, Temperature is absolutely consistent.

|current_time – Pressure_timestamp| = |2020 – 2010| = 10 msec which is less than or equal to Pressure_avi 20 msec. Hence, Pressure is absolutely consistent.

| Pressure_timestamp – Temperature_timestamp| = |2010 – 2000| = 10 msec which is less than or equal to R_rvi 20 msec. Hence, Temperature and Pressure are relatively consistent.

Hence, the relative consistency set R = {Temperature, Pressure} is temporally consistent.

************************

 

Go to Temporal Consistency in Real-time Database page

Go to REAL TIME DATABASE Home page

Optimistic Concurrency Control – Broadcast Commit (OCC-BC)

Optimistic Concurrency Control – Broadcast Commit (OCC-BC) in Real-Time Database.

Optimistic Concurrency Control – Broadcast Commit (OCC-BC)

This works as follows;

• Transactions are reading and writing the required data items freely without any blocking.

• When any of the transactions reaches commit, then that transaction broadcasts the decision to other concurrently ongoing transactions.

• Upon receiving this message, each ongoing transaction checks whether they have any conflict with the about-to-commit transaction.

• If any transactions find conflict with the about-to-commit transaction, then those transactions aborts and restarts immediately.

Example:

Let us assume that transactions T1, T2, and T3 are operating concurrently. Assume that transactions are working as follows;

T1 is working on data items A and B,

T2 is working on data items C, and

T3 is working on data items B and D.

These transactions can be of any size.

If T1 is reaching its commit statement, ie., the last statement of the transaction, it broadcasts the decision to other transactions.

T2 reads this message and finds no conflict because it is working on a different data item C. Hence it continues.

T3 reads this message and finds a conflict. T3 is also working on a data item B where T1 did something. Hence, T3 aborts and restarts.

Advantages:

• If a transaction reaches commit (the validating transaction) and broadcast its decision, the commit is guaranteed.

• The method detects conflicts earlier than the basic OCC algorithm, resulting in both, earlier restarts and less wasted resources, which increases the chances of meeting transactions’ deadlines.

Disadvantages:

• It does not consider priorities.

Note: OCC – Broadcast Commit does not considering priorities, hence it may not work well in the real-time database environment.  For example, low-priority transactions that reach validation unilaterally commit and cause conflicting higher priority transactions to be restarted. This may result in the affected high priority transactions missing their deadlines.

***********************

Go back to Optimistic Concurrency Control protocol page

Go to REAL TIME DATABASE Home page