I am not quire sure about case 3.

So my understanding is that there is a read/write conflict here. But since committing transaction has high priority, it means rd A has high priority than wr A. So it's ok here. If T1 commits first, then T0 should restart itself. Is this right?

Also what does forward progress mean here?

@bochet I think your explanation for case 3 is correct. The way optimistic detection works is that both T0 and T1 are trying to move forward along as if no conflicts have happened. Once one of them commits, the other threads recognize the conflict and have to abort and restart. So in this case, T0 has higher priority because it commits first.

Are there systems where writes always have higher priority than reads? Or the other way around? Regardless of which commits first?

@MichaelJordan If writes have higher priority, consider this: T0: write B, do a lot of jobs, read A, commit T1: write A, do a lot of jobs, read B, commit.

When T0 tries to commit right after T1 finish write A, T0 will find conflict on A. Because T1 writes on A, T1 has priority and T0 restart. Then T1 wants to commit and find T0 has restarted and wrote on B. T1 has to restart now. That process can loop forever.

@paramecinm: It wont loop forever. It's similar to case 3 above. A read by T0 after an uncommitted write by T1 will still proceed and T0 will commit as it is the first committing transaction and hence an old committed value read by T0 is alright for the system.

In case 2, why does T1 abort and restart instead of stalling while the T0 write commits?

What is the difference between 'aborts' and 'forward progress'? In both the cases, the threads seem to be restarting if a conflict is detected.

Professor Kayvon's comments on this link are really helpful for understanding what happens in case 3.

@asd and @bochet I think that forward progress just means that both transactions actually complete in this conflict detection scheme, versus the pessimistic scheme, where this same case caused a live lock in the system.

In case 3, T1 is not aborted is because write to A is in its private buffer. When T0 read A, it still observes the original A. Thus, T0 is still positioned in front of T1 in the timeline.

I agree with @cluo1. A key point in transactional memory is that no writes in the transaction are recognized by any other processors until the transaction commits. Because of this the read that T0 does in case 3 is not affected by the write of T1, since it hasn't been observed yet

@cluo1 +1 Otherwise only based on the write set we cannot tell whether T0 has read the version T1 modified

@pdp I think I give this example under the assumption of that write has higher priority to illustrate why that is a bad choice.

In order to maintain the invariant of all transactions appearing to be executed serially, do we think about this with respect to when the transactions are committed?

i.e. if transaction A is started before B, but B commits before A, then is the invariant we expect to see that the order of transactions was B -> A?

@Drizzle In case 2, T1 aborts and restarts instead of stalling because T1 already read A earlier and when T0 commits, the value of A that observed T1 earlier is no longer valid, so it must restart and read A again to get the updated value that T0 wrote. Stalling doesn't occur in Optimistic detection because the checks are only done when the commits occur, so each thread will just continue going until it is ready to commit or another thread tells it to restart. Stalling occurs during Pessimistic detection because at each load and store, it checks for conflicts and can tell immediately that another thread is trying to write and if it is reading, it will just wait for the write to commit instead of restarting. Make sure you understand Case 3 on slide 48.

@viveksri As per my understanding, the meaning of the serialization semantic is that you would like to see your instructions within one transaction executed serially. When a transaction commits and another aborts because of that, you are enforcing isolation between the transactions. For instance, if you wish that all your threads do a particular task, like a read, before any other transaction modifies it, you would put a fence/barrier to enforce that serialization. So, when you are working with transactions, the semantics of our code is such that it may not matter if B occurs before A or vice versa.

In case 3, what happens if T1 wr A occurs before T0 rd A? Is this ok since rd A commits first and thus receives priority?

Yes, it should be okay. Because T1 would anyway have to roll back and restart.

@asd Why would T1 have to rollback and restart? Isn't it ok because T0 was reading A, but T1 is writing to it?

With high contention, we could encounter starvation. In fact, high contention is inconsistent with the assumption of optimistic detection.

@1_1: Yes, you're right. My bad!

In case 3, transaction T0 can safely commit even when he knows that T1 has written to A, because of the isolation property of transaction. T0 won't see the change of T1, because T1 hasn't committed yet.