{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:00:10Z","timestamp":1767859210112,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540241294","type":"print"},{"value":"9783540304746","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30474-6_54","type":"book-chapter","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:40:22Z","timestamp":1267404022000},"page":"516-527","source":"Crossref","is-referenced-by-count":12,"title":["Lock-Free Parallel Algorithms: An Experimental Study"],"prefix":"10.1007","author":[{"given":"Guojing","family":"Cong","sequence":"first","affiliation":[]},{"given":"David","family":"Bader","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"crossref","unstructured":"Allemany, J., Felton, E.W.: Performance issues in non-blocking synchronization on shared-memory multiprocessors. In: Proc. 11th ACM Symposium on Principles of Distributed Computing, August 1992, pp. 125\u2013134 (1992)","DOI":"10.1145\/135419.135446"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, R.J., Woll, H.: Wait-free parallel algorithms for the union-find problem. In: Proc. 23rd Annual ACM Symposium on Theory of Computing, May 1991, pp. 370\u2013380 (1991)","DOI":"10.1145\/103418.103458"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Herlihy, M.P.: Wait-free data structures in the asynchronous PRAM model. In: Proc. 2nd Ann. Symp. Parallel Algorithms and Architectures (SPAA 1990), July 1990, pp. 340\u2013349 (1990)","DOI":"10.1145\/97444.97701"},{"issue":"4","key":"54_CR4","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1145\/179812.179902","volume":"41","author":"H. Attiya","year":"1994","unstructured":"Attiya, H., Lynch, N., Shavit, N.: Are wait-free algorithms fast? J. ACM\u00a041(4), 725\u2013763 (1994)","journal-title":"J. ACM"},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Cong, G.: Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs. In: Proc. Int\u2019l. Parallel and Distributed Processing Symp. (IPDPS 2004), Santa Fe, New Mexico (April 2004) (to appear)","DOI":"10.1109\/IPDPS.2004.1302953"},{"key":"54_CR6","unstructured":"Barnes, G.: Wait free algorithms for heaps. Technical Report TR-94-12-07, University of Washington (1994)"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Chor, B., Israeli, A., Li, M.: On processor coordination using asynchronous hardware. In: Proc. 6th ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada, pp. 86\u201397 (1987)","DOI":"10.1145\/41840.41848"},{"key":"54_CR8","unstructured":"Chung, S., Condon, A.: Parallel implementation of Bor\u00e5uvka\u2019s minimum spanning tree algorithm. In: Proc. 10th Int\u2019l. Parallel Processing Symp. (IPPS 1996), April 1996, pp. 302\u2013315 (1996)"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Zajicek, O.: The APRAM: incorporating asynchrony into the PRAM model. In: Proc. 1st Ann. Symp. Parallel Algorithms and Architectures (SPAA 1989), June 1989, pp. 169\u2013178 (1989)","DOI":"10.1145\/72935.72954"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"Cong, G., Bader, D.A.: Lock-free parallel algorithms: an experimental study. Technical report, Electrical and Computer Engineering Dept., University of Mexico (2004)","DOI":"10.1007\/978-3-540-30474-6_54"},{"issue":"1","key":"54_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1145\/7531.7533","volume":"34","author":"C. Dwork","year":"1987","unstructured":"Dwork, C., Dwork, D., Stockmeyer, L.: On the minimal synchronism needed for distributed consensus. J. ACM\u00a034(1), 77\u201397 (1987)","journal-title":"J. ACM"},{"issue":"2","key":"54_CR12","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C. Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM\u00a035(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"issue":"2","key":"54_CR13","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"M. Fischer","year":"1985","unstructured":"Fischer, M., Lynch, N.A., Paterson, M.S.: Impossibility of distributed commit with one faulty process. J. ACM\u00a032(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"key":"54_CR14","unstructured":"Fraser, K.A.: Practical lock-freedom. PhD thesis, King\u2019s College, University of Cambridge (September 2003)"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Goddard, S., Kumar, S., Prins, J.F.: Connected components algorithms for mesh-connected parallel computers. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 43\u201358. American Mathematical Society, Providence (1997)","DOI":"10.1090\/dimacs\/030\/03"},{"issue":"2","key":"54_CR16","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1109\/TC.1983.1676201","volume":"C-32","author":"A. Gottlieb","year":"1984","unstructured":"Gottlieb, A., Grishman, R., Kruskal, C.P., McAuliffe, K.P., Rudolph, L., Snir, M.: The NYU ultracomputer \u2014 designing a MIMD, shared-memory parallel machine. IEEE Trans. Computers\u00a0C-32(2), 175\u2013189 (1984)","journal-title":"IEEE Trans. Computers"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Greiner, J.: A comparison of data-parallel algorithms for connected components. In: Proc. 6th Ann. Symp. Parallel Algorithms and Architectures (SPAA 1994), Cape May, NJ, June 1994, pp. 16\u201325 (1994)","DOI":"10.1145\/181014.181021"},{"key":"54_CR18","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Moss, J.E.B.: Transactional memory: Architectural support for lock-free data structures. In: Proc. 20th Int\u2019l. Symposium in Computer Architecture, May 1993, pp. 289\u2013300 (1993)","DOI":"10.1145\/173682.165164"},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Herlihy, M.P.: A methodology for implementing highly concurrent data objects. In: Proc. 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, March 1990, pp. 197\u2013206 (1990)","DOI":"10.1145\/99164.99185"},{"issue":"1","key":"54_CR20","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M.P. Herlihy","year":"1991","unstructured":"Herlihy, M.P.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems\u00a013(1), 124\u2013149 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"54_CR21","doi-asserted-by":"crossref","unstructured":"Herlihy, M.P., Wing, J.M.: Axioms for concurrent objects. In: Proc. 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, January 1987, pp. 13\u201326 (1987)","DOI":"10.21236\/ADA200584"},{"key":"54_CR22","doi-asserted-by":"crossref","unstructured":"Hsu, T.-S., Ramachandran, V., Dean, N.: Parallel implementation of algorithms for finding connected components in graphs. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 23\u201341. American Mathematical Society, Providence (1997)","DOI":"10.1090\/dimacs\/030\/02"},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, A., Lumetta, S.S., Culler, D.E., Yelick, K.: Connected components on distributed memory machines. In: Bhatt, S.N. (ed.) Parallel Algorithms: 3rd DIMACS Implementation Challenge, October 17-19, 1994. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a030, pp. 1\u201321. American Mathematical Society, Providence (1997)","DOI":"10.1090\/dimacs\/030\/01"},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"LaMarca, A.: A performance evaluation of lock-free synchronization protocols. In: Proc. 13th Annual ACM Symposium on Principles of Distributed Computing, August 1994, pp. 130\u2013140 (1994)","DOI":"10.1145\/197917.197975"},{"issue":"11","key":"54_CR25","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/359863.359878","volume":"20","author":"L. Lamport","year":"1977","unstructured":"Lamport, L.: Concurrent reading and writing. Communications of the ACM\u00a020(11), 806\u2013811 (1977)","journal-title":"Communications of the ACM"},{"issue":"2","key":"54_CR26","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1145\/69624.357207","volume":"5","author":"L. Lamport","year":"1983","unstructured":"Lamport, L.: Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems\u00a05(2), 190\u2013222 (1983)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"54_CR27","doi-asserted-by":"crossref","unstructured":"Lanin, V., Shaha, D.: Concurrent set manipulation without locking. In: Proc. 7th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 1988, pp. 211\u2013220 (1988)","DOI":"10.1145\/308386.308442"},{"key":"54_CR28","doi-asserted-by":"crossref","unstructured":"Massalin, H., Pu, C.: Threads and input\/output in the synthesis kernel. In: Proc. 12th ACM Symposium on Operating Systems Principles, December 1989, pp. 191\u2013201 (1989)","DOI":"10.1145\/74850.74869"},{"key":"54_CR29","volume-title":"The LEDA Platform of Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"issue":"1","key":"54_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jpdc.1998.1446","volume":"51","author":"M.M. Michael","year":"1998","unstructured":"Michael, M.M., Scott, M.L.: Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors. Journal of Parallel and Distributed Computing\u00a051(1), 1\u201326 (1998)","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"54_CR31","doi-asserted-by":"crossref","unstructured":"Moret, B.M.E., Shapiro, H.D.: An empirical assessment of algorithms for constructing a minimal spanning tree. In: DIMACS Monographs in Discrete Mathematics and Theoretical Computer Science: Computational Support for Discrete Mathematics, vol.\u00a015, pp. 99\u2013117. American Mathematical Society, Providence (1994)","DOI":"10.1090\/dimacs\/015\/09"},{"key":"54_CR32","doi-asserted-by":"crossref","unstructured":"Shavit, N., Touitou, D.: Software transactional memory. In: Proc. 14th annual ACM Symposium on Principles of Distributed Computing, August 1995, pp. 204\u2013213 (1995)","DOI":"10.1145\/224964.224987"},{"issue":"1","key":"54_CR33","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Shiloach, Y., Vishkin, U.: An O(logn) parallel connectivity algorithm. J. Algs.\u00a03(1), 57\u201367 (1982)","journal-title":"J. Algs."},{"issue":"2","key":"54_CR34","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/62.2160","volume":"31","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Van Leeuwen, J.: Worst-case analysis of set union algorithms. J. ACM\u00a031(2), 245\u2013281 (1984)","journal-title":"J. ACM"},{"key":"54_CR35","doi-asserted-by":"crossref","unstructured":"Tsigas, P., Zhang, Y.: A simple, fast and scalable non-blocking concurrent FIFO queue for shared memory multiprocessor systems. In: Proc. 13th Ann. Symp. Parallel Algorithms and Architectures (SPAA 2001), September 2001, pp. 134\u2013143 (2001)","DOI":"10.1145\/378580.378611"},{"key":"54_CR36","unstructured":"Valois, J.: Lock-free data structures. PhD thesis, Rensselaer Polytechnic Institute (May 1995)"},{"key":"54_CR37","doi-asserted-by":"crossref","unstructured":"Valois, J.D.: Lock-free linked lists using compare-and-swap. In: Proc. 14th Annual ACM Symposium on Principles of Distributed Computing, August 1995, pp. 214\u2013222 (1995)","DOI":"10.1145\/224964.224988"}],"container-title":["Lecture Notes in Computer Science","High Performance Computing - HiPC 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30474-6_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T13:23:09Z","timestamp":1558876989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30474-6_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241294","9783540304746"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30474-6_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}