In this case, thread 0 plans to delete A and set the B at the top. However, if thread 1 add D between A and B, the thread 0 removes not only A, but also D. This is a different result from the expected result: D->B->C, I guess.

What would happen if B was also removed from the stack by thread 1 before pushing D and A? Would thread 0 still only check if the top was A, then move "top" to the address of B (which is completely removed from the stack and could be garbage memory)?

This slide shows an example scenario of the ABA problem. In this scenario, thread 0 wants to pop node A off the stack. To do this (function on previous slide), it first reads the top of the stack, stores old_top as A, then calls compare-and-swap, which checks that the node at the top of the stack is still A, and if so, proceeds to replace the top with the new_top B because it comes after A. However, where the trick is if thread 1 preempts thread 0 between the two checks. In this scenario, thread 1 manages to start running right after thread 0 initiates the pop but hasn't actually modified the stack yet. Thread 1 sneakily pops off A, pushes on D, then pushes A back. Then, when control is returned to thread 0, it is still in the middle of its pop operation. It checks that the top node is still A, so it falsely believes that the stack is the same as when it first checked, and proceeds to pop off A and set the new top to B. In doing so, D disappears from the stack! D was "hidden" in the stack, leading it to get lost, and the stack therefore corrupted.

According to Wikipedia, this problem can occur if the pop operation uses the "value is the same" condition to decide whether it is safe to pop. In this slide however, it is "address is the same" instead. Either way, the ABA problem can be illustrated.

@jlara I don't think the atomic compare and swap checks for the validity of the replacement value (at least in the code we were shown), so I think it would just throw some garbage on top of the stack, like you said.

The ABA problem entails a thread attempting to pop A of the top of a stack, making the new top B, but before it does this having other threads add another value to the stack and then adding the original A back to the stack. Because the first thread only decides to execute its pop based on whether the top element is what it expects to remove, it will go forward with making the top of the stack B, even though this removes the intermediately added value. The root of the problem is that the element to be changed being unmodified does not prove that the data structure itself is unmodified. For this additional information needs to be considered. However, the obvious solution to this problem would require atomic memory operations not commonly provided by CPUs.

One way to overcome the ABA problem is to add a counter to the stack so that we can check that the number of elements did not change after our test, but we would need a double compare and swap test to make both tests atomic.

It seems that we can also avoid this problem by making sure every node is unique, e.g. attaching an unique identifier that is never recycled to every node (in addition to its value) and compare-and-swap on that. This obviously comes with additional memory overhead though.