I wonder about the step of "remove duplicates from result". I think if the UPDATE function is indeed atomic, then there shouldn't be any duplicates in result.

Same confusion as @blipblop: since we're using compare-and-swap, and checked that parent[d] is -1 before setting the new value, we're only traversing each node once. Why do we still need to de-duplicate here?

I think that the remove duplicates is needed because we cannot assume anything about the COND and UPDATE functions.

Agree with @l-henken. In later part of this lecture, Kayvon said "It is not an implementation of BFS. It is the implementation of edge map, which works for any function F or C that the application provides. With certain C and certain F, we can implement BFS. "