The move to multicore processors as our standard computing platform will force major changes in the way we design parallel software, and in particular in the way we design and use concurrent data structures. The goal of our research was to develop new concurrent data structures, not as lock-based or lock-free versions of sequential data structures, but rather from scratch as high throughput concurrent structures. We reevaluated the way in which concurrent data struc-tures are specied, implemented, and used in parallel programs. We then developed new types of relaxed shared concurrent objects: objects that have relaxed specications for which we then developed decentralized randomized implementations that are scalable since they have low overall communication and memory access rates.

We developed a collection of data structures solving a variety of tasks. The SkipTrie, a low-depth concurrent search structure that allows fast randomized predecessor queries access without rebalancing. The Leaplist: a skiplist stype randomized concurrent data structrue using hardware transactions that allows efficient range queries.  We also developed a new randomized Loose Renaming algorithm that takes only O(log log n) time to rename n items. We developed a new types of NUMA-aware reader-writer locks that allow for better scalaibility in concurrent data structure design. We develoepd the LevelArray: a fast, long-lived renaming algorithm. We proved mathematically that many lock-free concurrent algorithms are wait-free in practice without the need to restucture them. This introduces major potential saving in the cost of designing concurrent data structures, as programmers can avoid the overhead of wait-free algorithm design and still get all its benefits from lock-free ones. Finally, we developed the SprayList: a scalable relaxed priority queue based on randomization. For most of these data structures we provided code, available on the internet for public use. 

We belive that we have clearly shown that one can develop competitive concurrent algorithms, ones that greatly improve over traditional data structures parallelized using locks. The key techniques we developed exposed the crucial role of randomization and the use of relaxed specifications. 

Commercial software developers are in desperate need of data structures that scale, and teh availability of structures and techniques developed in the project available to them will greatly help in making applications make full use of the parallelism offered by multicore machines.