No conflicts of the read and write sets from transaction A and B indicate a possible concurrency.

What happens when it's impossible to know what needs to be written before the data is read? For example, inserting into a binary tree as shown.

@anon33 I think this becomes clearer if we consider the material from later in the lecture where we looked at ways that transactional memory is implemented. With different schemed for conflict detection and data versioning, we can basically attempt to carry out two transactions in parallel and build up their read and write sets dependent on the memory operations that are carried out within the transaction. Then, when a transaction goes to commit, it has to compare its read/write set to other pending transactions to determine whether or not there has been a potential overlap. So I think the idea is we don't just magically know when there is data that needs to be read before it is written – we try running the appropriate memory transactions for the operation and then we use a conflict detection policy upon transaction commit to determine whether the Tx can commit or needs to abort/restart.

Was also wondering about what @anon33 said. Thanks @nickbowman for the explanation.

For a data structure like this where a node is often represented as a node with pointers to children, it seems we would be likely to run into false sharing if transactions occur at cache-line granularity, and we would still have write-write conflicts. Maybe a good way around this would be to align individual nodes such that children pointers land on different cache lines

I think @nickbowman's comment describes an optimistic conflict detection policy. Using a pessimistic conflict detection policy and presumably eager versioning with this example, we would check at the time of reading or writing to each node, rather than after the commit. Since there's no conflict, the pessimistic policy seems to perform worse.