Block-STM - Why do we need this condition "when a transaction aborts, all higher transactions are scheduled for re-validation."

Question

I just finished reading about Block-STM and I have a question that I can’t seem to understand at all. I’ve studied from these two links:

• https://arxiv.org/pdf/2203.06871.pdf
• https://malkhi.com/posts/2022/04/block-stm/

What I don’t understand is this part:

Block-STM introduces a collaborative scheduler, which coordinates the validation and execution tasks among threads. The preset serialization order dictates that the transactions must be committed in order, so a successful validation of an incarnation does not guarantee that it can be committed. This is because an abort and re- execution of an earlier transaction in the block might invalidate the incarnation read-set and necessitate re-execution. Thus, when a transaction aborts, all higher transactions are scheduled for re-validation.

With the example in the paper, I understand that the validation of tx2 fails because it might read from the same memory location that is written to by tx1, so there’s nothing wrong here, and I can understand that. But why does tx3 need to be revalidated as well, even though it passes the validation process? Well, according to the algorithm, it seems like if tx3 passes the validation phase, this means that it should not depend on tx1 or tx2 at all (it doesn’t access the location where tx1 and tx2 write the data). So, why does tx3 need to be revalidated? According to the part I quoted from the paper, it says:

This is because an abort and re-execution of an earlier transaction in the block might invalidate the incarnation read-set and necessitate re-execution. Thus, when a transaction aborts, all higher transactions are scheduled for re-validation.

But then, I think an earlier transaction can cause transactions after it to be re-executed if and only if the transactions after it read from the same memory that the earlier transaction is trying to write to. So, I can’t understand why we need “when a transaction aborts, all higher transactions are scheduled for re-validation” this condition at all.

Could anybody give me an example of the case that a transaction can cause the transactions after them even if they are not access the same memory as the earlier transaction.

Answer 1

I believe the answer is that because transactions and smartcontracts contain arbitrary logic, there's a chance that a reexecution of tx_2 will write a new location based on the information it read from tx_1. And there's a possibililty that tx_3 has already read from that location so there's a need to revalidate it.

I also struggled with this at first but when you think of the fact that the VM is designed to handle arbitrary logic then it makes sense.

I'm happy to jam on discussions about Block-STM if you have further questions, you can DM me on Telegram/twitter here: fikunmi_ap