  In this paper, we study the partitioning of a context-aware shared memory
data structure so that it can be implemented as a distributed data structure
running on multiple machines. By context-aware data structures, we mean that
the result of an operation not only depends upon the value of the shared data
but also upon the previous operations performed by the same client. While there
is substantial work on designing distributed data structures, designing
distributed context-aware data structures has not received much attention.
  We focus on singly-linked lists as a case study of the context-aware data
structure. We start with a shared memory context-aware lock-free singly-linked
list and show how it can be transformed into a distributed lock-free
context-aware singly-linked list. The main challenge in such a transformation
is to preserve properties of client-visible operations of the underlying data
structure. We present two protocols that preserve these properties of
client-visible operations of the linked list. In the first protocol, the
distribution is done in the background as a low priority task, while in the
second protocol the client-visible operations help the task of distribution
without affecting client latency. In both protocols, the client-visible
operations remain lock-free. Also, our transformation approach does not utilize
any hardware primitives (except a compare-and-swap operation on a single word).
We note that our transformation is generic and can be used for other lock-free
context-aware data structures that can be constructed from singly-linked lists.
