  We present a general methodology for establishing the impossibility of
implementing certain concurrent objects on different (weak) memory models. The
key idea behind our approach lies in characterizing memory models by their
mergeability properties, identifying restrictions under which independent
memory traces can be merged into a single valid memory trace. In turn, we show
that the mergeability properties of the underlying memory model entail similar
mergeability requirements on the specifications of objects that can be
implemented on that memory model. We demonstrate the applicability of our
approach to establish the impossibility of implementing standard distributed
objects with different restrictions on memory traces on three memory models:
strictly consistent memory, total store order, and release-acquire. These
impossibility results allow us to identify tight and almost tight bounds for
some objects, as well as new separation results between weak memory models, and
between well-studied objects based on their implementability on weak memory
models.
