Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms
Abstract:
We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.
Information query
Patent Agency Ranking
0/0