Distributed Computing Wikiclass | Tutorial / Concurrency Control

A Distributed Computing Tutorial by Steven Choy

Concurrency Control of Transactions - 2PL

Consider two transactions T and U as defined in the following.

   T: y = read(k); x = read(i); write(j,22);
   U: write(i,33); write(j,44);

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

Concurrency Control of Transactions - OCC

Consider optimistic concurrency control as applied to two transactions T and U as defined in the following.

   T: x = read(i); write(j,66);
   U: write(i,77); write(j,88);

Suppose the transactions T and U are active at the same time as one another. Describe the outcome in each of the following cases. Note that in each case your description must include whether transactions T and U commit or abort and why. Remember that writes are not carried out until after validation.

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

Concurrency Control of Transactions

How does time-stamp ordering (TSO) ensure serializability?
What are advantages and disadvantages of the optimistic concurrency control method for controlling concurrent access to shared data?
Compare two-phase locking, optimistic concurrency control, and timestamp ordering methods for controlling concurrent access to shared data.

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.
State one advantage and one disadvantage of wound-wait over wait-die.
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.
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.
What is the main difference between deadlock prevention and deadlock avoidance in handling deadlocks in distributed systems?

Suggested answers are available here.