Not sure if I totally understand Case 2 here. So does T1 attempt to perform a rd A, but hasn't been able to do it because of conflict, stalls, and then rd A? Or does it do a rd A, detects a conflict, and stall, and then do everything after (not including) rd A?

Another scenario where no progress can be made would be T0 wrA+rdB and T1 wrB+rdA which would result in deadlock.

The fourth scenario is similar to a livelock, where there is no meaning progress made even though the two transactions are constantly trying to restart and write.

Also note that pessimistic detection works well with eager versioning which uses an undo log.

@jxx1998 I think it's the first case you described.

I have another question about case 4: if our policy is just "writer wins", why does T1's wr A have higher priority than T0's wrA? They're performing the same operation.

@haiyuem I think the policy would be more explicitly stated as "when a conflict is detected, the writing transaction wins." With this interpretation of the contention management scheme, we can reason that T1's wr A aborts T0 because T1 was the writing transaction at the time of conflict! Hope that helps :).

What are examples of methods to detect livelock? Would we just check if we've had failure for the same reasons X times in a row, and if so, stall one transaction while the other completes?

@harrymellsop I think that could be one method of detection, but we would need to make sure that the stalled transaction gets priority over any other transaction (we could just forget "writer wins"?) after in order to prevent starvation.

I originally thought "failure" is due to hardware/network issues. This is a good example that shows failure also arises from memory conflicts.

Due to the nature of transaction failure recovery, we can not make a "large" transaction where a large amount of memory is required. It is interesting to contrast with Spark: Spark tackles failures by "checkpointing" and can work with large memories. Just wondering if there are frameworks/models that combine these two ideas.

Is the "stall" (for example in example 2) waits until another transaction committed? Will the commit of one transaction resumes another transaction that has been stalled or the stalled transaction just resumes randomly (and maybe check again)?

with the optimistic detection discussed in p49, the scenario in case4 would goes like: T0 commit -> T1 restart -> T1 commit, without running into livelock.

Is it possible to design a pessimistic detection scheme that does have forward progress guarantees? Or is pessimistic detection just not a valid scheme to use?

I have the same question as @tp. In case 4, could T0 stall until T1 is done and then restart to avoid livelock?

We can use a randomized selection of which thread is allowed to commit or we can assign a higher priority to the transaction that has more restarts to avoid the livelock. Between the two the second approach would help avoid starvation.

A useful comment Kayvon made during lecture: One can ask "how is isolation guaranteed in an eager versioning scheme, because it seems like if a thread writes eagerly, some other thread might observe those writes before the transaction is complete." However, if other threads are always PESSIMISTICALLY checking for conflicts, aborts, and pauses, before reading any values, then it will not allow itself to observe partial results. So effectively, all threads in transactions will not observe partial values, even if the state of memory contains partial values.

Checking for a conflict in an eager scheme amounts to checking the addresses in other threads' undo logs.

Going off @blipblop's comment, what happens if we combine optimistic and pessimistic operations? For example, STM read is optimistic and STM write is pessimistic, so is isolation still guaranteed? My understanding is that the answer is yes. Since write is pessimistic, even if read is optimistic then partial values will not be observed by an optimistic read thread.

In case #4, when a thread writes to A, it causes the other thread to abort the current transaction. So if two threads are doing Wr A in a transaction, it is possible that no thread can make progress. In optimistic detection, the thread which make the commit first can always make progress.

@danieljim I think you're right that isolation is guaranteed, but I don't think the same is true in the converse.

@danieljm @gleb I'm not sure if that interpretation is 100% accurate. If we have eager data versioning with optimistic reads and pessimistic writes, then transactions will actually observe partial values that another transaction has updated. The key thing here is that when the transaction that observed partial values tries to commit, it will need to abort. Thus, the isolate constraint is really saying that you can be certain that successfully committed transactions did not observe partial results.