What is a swap-with-memory instruction?
I would assume the fetch_and_store instruction is meant. Look at the footnotes on page 2:


  1) Fetch-and-store exchanges a register with memory.


Keep in mind that this paper is over 20 years old, so the terminology can seem unfamiliar. However, often the semantic of the operations/instructions used in such papers are described in detail somewhere in the text.