1981 Optimistic Methods for Concurrency Control

Back to Research-Papers

concurrency control in database management systems handles critical sections of code in multi-user systems

For each action in a transaction i,

read (Oj):
  if WTS(Oj) > TS(Ti) abort // a more recent transaction has changed the value 
  else RTS(Oj) = max(RTS(Oj), TS(Ti))

write (Oj):
  if RTS(Oj) > TS(Ti) abort     // more recent transaction is already using the old value
  else if WTS(Oj) > TS(Ti) skip // useless write, thomas write rule
  else WTS(Oj) = TS(Ti)         // and update

  for each (oldOj, oldWTS(Oj)) in OLD(Ti)
    if WTS(Oj) == TS(Ti) then restore Oj and WTS(Oj) // undo all actions performed in transaction

Problems with locks: deadlock, livelock

Two directions are taken to try and find accurate high concurrency protocols:

  1. find deadlock-free locking protocol
  2. elminate the use of locks