000217219 001__ 217219
000217219 005__ 20190317000416.0
000217219 0247_ $$2doi$$a10.1145/2851141.2851146
000217219 02470 $$2ISI$$a000393580200019
000217219 037__ $$aCONF
000217219 245__ $$aOptimistic Concurrency with OPTIK
000217219 269__ $$a2016
000217219 260__ $$bACM Press$$c2016$$aNew York, New York, USA
000217219 300__ $$a12
000217219 336__ $$aConference Papers
000217219 520__ $$aWe introduce OPTIK, a new practical design pattern for designing and implementing fast and scalable concurrent data structures. OPTIK relies on the commonly-used technique of version numbers for detecting conflicting concurrent operations. We show how to implement the OPTIK pattern using the novel concept of OPTIK locks. These locks enable the use of version numbers for implementing very efficient optimistic concurrent data structures. Existing state-of-the-art lock-based data structures acquire the lock and then check for conflicts. In contrast, with OPTIK locks, we merge the lock acquisition with the detection of conflicting concurrency in a single atomic step, similarly to lock-free algorithms. We illustrate the power of our OPTIK pattern and its implementation by introducing four new algorithms and by optimizing four state-of-the-art algorithms for linked lists, skip lists, hash tables, and queues. Our results show that concurrent data structures built using OPTIK are more scalable than the state of the art.
000217219 6531_ $$aconcurrent data structures
000217219 6531_ $$aconcurrency
000217219 6531_ $$ascalability
000217219 6531_ $$amulti-core
000217219 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000217219 700__ $$aTrigonakis, Vasileios$$g210576$$0245903
000217219 7112_ $$d12-16 03 2016$$cBarcelona, Spain$$a21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16
000217219 773__ $$tProceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP '16
000217219 8564_ $$uhttps://dl.acm.org/citation.cfm?id=2851146$$zURL
000217219 8564_ $$uhttps://github.com/LPD-EPFL/ASCYLIB$$zURL
000217219 8564_ $$uhttp://lpd.epfl.ch/site/optik$$zURL
000217219 8564_ $$uhttps://infoscience.epfl.ch/record/217219/files/PPoPP16_OPTIK.pdf$$zPublisher's version$$s442142$$yPublisher's version
000217219 909C0 $$xU10407$$0252114$$pDCL
000217219 909CO $$ooai:infoscience.tind.io:217219$$qGLOBAL_SET$$pconf$$pIC
000217219 917Z8 $$x210576
000217219 937__ $$aEPFL-CONF-217219
000217219 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000217219 980__ $$aCONF