The Taub Faculty of Computer Science Events and Talks

The study and design of concurrent data structures has mostly focused on verifying their correctness and proving general progress guarantees. In contrast, very little work has been done on analyzing the running time of these data structures, possibly due to a lack of a good model under which to perform such analysis. We take a step in this direction by presenting a concurrent relaxed counter which we show how to use to keep track of dependencies in a series-parallel DAG, something which is vital in the implementation of nested parallelism. Our data structure is based on work by Ellen et al. on Scalable Non-Zero Indicators (SNZI). We prove that our data structure is efficient; in particular we prove that under a relaxed concurrency model (one that is often assumed in parallel computation), any operation on our counter takes amortized constant time (i.e. independent of the number of concurrent operations and the length of the history), even when accounting for contention. Joint work with Umut Acar and Mike Rainey.