Abstract
We address a fundamental issue of interfaces that arises in the context of cloud computing; namely, what does it mean for a replicated and distributed implementation of a data structure to satisfy its standard sequential speci?cation. We describe an approach that liberalizes the linear and totally ordered time regime of linearizability to partial orders. We establish three key properties: * Expressiveness: we account for a wide range of extant replicated implementations of distributed data structures. * Composition: we show how to reason about composite data structures in terms of their components. * Abstraction: we show how a client's view of the distributed data structure can be simplified to reasoning with the sequential specification. This is joint work with James Riely.