We extend state-of-the-art lock-free linked lists by building linked lists with special care for locality of traversals. These linked lists are built of sequences of entries that reside on consecutive chunks of memory. When traversing such lists, subsequent entries typically reside on the same chunk and are thus close to each other, e.g., in same cache line or on the same virtual memory page. Such cache-conscious implementations of linked lists are frequently used in practice, but making them lock-free requires care. The basic component of this construction is a chunk of entries in the list that maintains a minimum and a maximum number of entries. This basic chunk component is an interesting tool on its own and may be used to build other lock-free data structures as well.

Unable to display preview. Download preview PDF.

Authors and Affiliations

1. Dept. of Computer Science, Technion - Israel Institute of Technology, Israel

   Anastasia Braginsky & Erez Petrank

Editors and Affiliations

1. Microsoft Research Silicon Valley, 1065 La Avenida – bldg. 6, 94043, Mountain View, CA, USA

   Marcos K. Aguilera

2. School of Computing, National University of Singapore, COM2-04-25, 15 Computing Drive, 117418, Republic of Singapore

   Haifeng Yu

3. 458 Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, MC-228, 1308 West Main Street, 61801, Urbana, IL, USA

   Nitin H. Vaidya

4. Alcatel-Lucent Technologies, Manyata Technology Park, Nagawara, 560045, Bangalore, India

   Vikram Srinivasan

5. ECE Department, Duke University, 130 Hudson Hall, Box 90291, 27708, Durham, NC, USA

   Romit Roy Choudhury

Reprints and permissions

© 2011 Springer-Verlag Berlin Heidelberg

Policies and ethics