  Composing together the individual atomic methods of concurrent
data-structures (cds) pose multiple design and consistency challenges. In this
context composition provided by transactions in software transaction memory
(STM) can be handy. However, most of the STMs offer read/write primitives to
access shared cds. These read/write primitives result in unnecessary aborts.
Instead, semantically rich higher-level methods of the underlying cds like
lookup, insert or delete (in case of hash-table or lists) aid in ignoring
unimportant lower level read/write conflicts and allow better concurrency. In
this paper, we adapt transaction tree model in databases to propose OSTM which
enables efficient composition in cds. We extend the traditional notion of
conflicts and legality to higher level methods of cds using STMs and lay down
detailed correctness proof to show that it is co-opaque. We implement OSTM with
concurrent closed addressed hash-table(HT-OSTM)and list (list-OSTM) which
exports the higher-level operations as transaction interface. In our
experiments with varying workloads and randomly generated transaction
operations, HT-OSTM shows speedup of 3 to 6 times and w.r.t aborts HT-OSTMis 3
to 7 times better than ESTM and read/write based STM, respectively. Where
as,list-OSTM outperforms state of the art lock-free transactional list, NOrec
STM list and boosted list by 30% to 80% across all workloads and scenarios.
Further,list-OSTM incurred negligible aborts in comparison to other techniques
considered in the paper.
