  A data structure is called history independent if its internal memory
representation does not reveal the history of operations applied to it, only
its current state. In this paper we study history independence for concurrent
data structures, and establish foundational possibility and impossibility
results. We show that a large class of concurrent objects cannot be implemented
from smaller base objects in a manner that is both wait-free and history
independent; but if we settle for either lock-freedom instead of wait-freedom
or for a weak notion of history independence, then at least one object in the
class, multi-valued single-reader single-writer registers, can be implemented
from smaller base objects, binary registers.
  On the other hand, using large base objects, we give a strong possibility
result in the form of a universal construction: an object with $s$ possible
states can be implemented in a wait-free, history-independent manner from
compare-and-swap base objects that each have $O(s + 2^n)$ possible memory
states, where $n$ is the number of processes in the system.
