Basic TO Algorithm question

Two transactions T1 and T2. Initially RTS = 0 and WTS = 0 for data items X, Y

Timestamps are as follows: TS (T1)=10 and TS (T2)=20

T1

T2

TS(T1)=10

TS(T2)=20

1. A * 1 = Read(X)

A 1=A1-k

3. Write(X, A1)

1. A * 1 = Read(X)

2. A 1=A1^ * 1.01

3. Write(X, A1)

4. A^ 2 =R aad (V)

5. A 2=A2+k

6. Write(Y, A2)

4. A * 2 = Read(Y)

5. A 2=A2^ * 1.01

6. Write(Y, A2)

Discuss whether the following schedule is serializable or not? Justify your answer using Basic TO Algorithm.

1 answer

To determine if the given schedule is serializable or not, we can use the Basic TO Algorithm.

The Basic TO Algorithm works by constructing a precedence graph, where each transaction is represented by a node and there is an edge between two nodes if a conflict exists between the two corresponding transactions. A schedule is serializable if and only if the precedence graph is acyclic.

Let's go step by step and identify the precedences and conflicts between the transactions:

Step 1:
- T1 reads X
- T2 reads X
No conflicts or precedences exist between T1 and T2 at this point.

Step 2:
- T1 writes X
- T2 writes X
There is a conflict between T1 and T2 since T1 writes X before T2 writes X.

Step 3:
- T1 reads X
- T2 reads X
There is a precedence between T2 (20) and T1 (10) since T2 has a higher timestamp than T1.

Step 4:
- T1 writes X
- T2 writes X
There is a conflict between T1 and T2 since T1 writes X before T2 writes X.

Step 5:
- T1 reads Y
- T2 reads Y
No conflicts or precedences exist between T1 and T2 at this point.

Step 6:
- T1 writes Y
- T2 writes Y
There is a conflict between T1 and T2 since T1 writes Y before T2 writes Y.

Based on the analysis above, we can construct the precedence graph as follows:
T1 (10) -> T2 (20)

As we can see, there is a cycle in the precedence graph, which means that the schedule is not serializable.

In conclusion, the given schedule is not serializable according to the Basic TO Algorithm.