  A key way to construct complex distributed systems is through modular
composition of linearizable concurrent objects. A prominent example is shared
registers, which have crash-tolerant implementations on top of message-passing
systems, allowing the advantages of shared memory to carry over to
message-passing. Yet linearizable registers do not always behave properly when
used inside randomized programs. A strengthening of linearizability, called
strong linearizability, has been shown to preserve probabilistic behavior, as
well as other hypersafety properties. In order to exploit composition and
abstraction in message-passing systems, it is crucial to know whether there
exist strongly-linearizable implementations of registers in message-passing.
This paper answers the question in the negative: there are no
strongly-linearizable fault-tolerant message-passing implementations of
multi-writer registers, max-registers, snapshots or counters. This result is
proved by reduction from the corresponding result by Helmi et al. The reduction
is a novel extension of the BG simulation that connects shared-memory and
message-passing, supports long-lived objects, and preserves strong
linearizability. The main technical challenge arises from the discrepancy
between the potentially minuscule fraction of failures to be tolerated in the
simulated message-passing algorithm and the large fraction of failures that can
afflict the simulating shared-memory system. The reduction is general and can
be viewed as the inverse of the ABD simulation of shared memory in
message-passing.
