Full Abstraction Without Synchronization Primitives

Using game semantics, we prove a full abstraction result (with respect to the may-testing preorder) for Idealized Algol augmented with parallel composition (IA||). Although it is common knowledge that semaphores can be implemented using shared memory, we find that semaphores do not extend IA|| conservatively. We explain the reasons for the mismatch.