Distributed Computing Wikiclass | TutorialAnswer / ConcurrencyControl

Concurrency Control of Transactions - 2PL

Interleaving of transactions T and U that are serially equivalent but not with two-phase locking

    T1: y = read(k);
    T2: x = read(i);
                      U1: write(i,33);
    T3: write(j,22);
                      U2: write(j,44);

Interleaving of transactions T and U that are serially equivalent but not with two-phase locking

                      U1: write(i,33);
    T1: y = read(k);
    T2: x = read(i);
                      U2: write(j,44);
    T3: write(j,22);

Interleaving of transactions T and U that are serially equivalent and with two-phase locking

    T1: y = read(k);
    T2: x = read(i);
    T3: write(j,22);
                      U1: write(i,33);
                      U2: write(j,44);

Interleaving of transactions T and U that are serially equivalent and with two-phase locking

    T1: y = read(k);
                      U1: write(i,33);
                      U2: write(j,44);
    T2: x = read(i);
    T3: write(j,22);

Concurrency Control of Transactions - OCC

T’s request to commit comes first and backward validation is used

T’s read(i) is compared with writes of overlapping committed transactions, so Transaction T is OK (as U has not yet committed).

Transaction U is OK as no read operations involved.

U’s request to commit comes first and backward validation is used

Transaction U is OK as no read operations involved.

T’s read(i) is compared with writes of overlapping committed transactions (U’s write(i)), so Transaction T FAILS.

T’s request to commit comes first and forward validation is used

T’s write(j) is compared with reads of overlapping active transactions (U), so Transaction T is OK.

U’s write(i) is compared with reads of overlapping active transactions (none), so Transaction U is OK (as T is no longer active).

U’s request to commit comes first and forward validation is used.

U’s write(i) is compared with reads of overlapping active transactions (T’s read(i)), so Transaction U FAILS.

T’s write(j) is compared with reads of overlapping active transactions (none), so transaction T is OK.

Concurrency Control of Transactions

How does time-stamp ordering (TSO) ensure serializability?

In TSO, the time at which a transaction starts is associated with the transaction, and is recorded by every object involved with each operation invoked by the transaction. One serializable order is imposed on the operations by the time-stamp order. Thus, if transaction T2 attempts to invoke an operation that conflicts with an operation already started by transaction T1, and the time-stamp of T2 is earlier than that of T1, then T2 is aborted.

Advantage of OCC: It is deadlock free / it allows for maximum parallelism.
Disadvantage of OCC: A substantial amount of work might have to be repeated when a transaction aborts. Transactions that need a lot of resource may need a lot of time to finish.

Deadlock detection and prevention in distributed systems

Wait-die and wound-wait are two practical algorithms for distributed deadlock prevention.

Describe the common idea shared by these two algorithms.

When a process is about to block waiting for a resource that another process is using, a higher priority is given to an order process rather than a young one.

State one advantage and one disadvantage of wound-wait over wait-die.

Advantage: no process is killed. Disadvantage: a younger process may need to wait for a long time to complete its execution.

A process with transaction timestamp 64 needs a resource held by a process with transaction timestamp 82. Explain what happens (1) when wait-die algorithm is used; and (2) when wound-wait algorithm is used.

In (1), The process with transaction timestamp 64 waits for the younger process. In (2), The process with transaction timestamp 64 preempts the resource from the younger one (timestamp 82) and the younger one has to wait.

Why the methods wait-die and wound-wait cannot apply in the deadlock prevention if processes are allowed to hold more than one resource? Give one example to explain your reason.

It is because if a process holds more than one resource, it is impossible to identify the process is old or young and thus it cannot conclude what action should be taken.

Consider a process wants to hold two resources. One resource is held by a younger process and another resource is held by an older process. For wait-die algorithm, it is meaningless to wait for the younger process and die for the older process at the same time. Also for wound-wait algorithm, it cannot take the advantage of preempting the younger process because the process has to wait for the older process.

What is the main difference between deadlock prevention and deadlock avoidance in handling deadlocks in distributed systems?

Deadlock prevention is to add an algorithm for transaction to follow. It may result in significant overhead and some transactions may abort to prevent a deadlock occurs. In deadlock avoidance, we do not touch transactions but resources. We want to take care of the distribution of the resources and avoid deadlocks by computing when they will happen.