A simple and therefore highly usable non-blocking implementations of
linked-lists can be provided using read, write, and CAS operations.
Several realizations of linked-list based data-structures are described,
which are non-blocking, linearizable, and exhibit disjoint-access for
most operations. In other words, the realizations are non-blocking and
linearizable while maintaining the property that operations on disjoint
parts of the list do not interact, effectively lowering contention and
increasing concurrency. We implement three exemplary data structures:
sets, multi-sets, and ordered-sets. The exemplary implementations support
insert, remove, and find operations, with natural semantics. An
ordered-set implementation supports an additional removeGE operation.