An Impossibility Result on Strong Linearizability in Message-Passing Systems

We prove that there is no 1-resilient strongly linearizable implementation of a weak object in asynchronous message-passing systems. This object, that we call Test-\emph{or}-Set (ToS), allows a single distinguished process to apply the set operation once, and a \emph{different} distinguished process to apply the test operation also once. Since this weak object can be directly implemented by a single-writer single-reader (SWSR) register (and other common objects such as max-register, snapshot, counter, test-and-set, queue, stack, etc...), this result implies that there is no 1-resilient strongly linearizable implementation of a SWSR register (and of these other objects) in message-passing systems.