A Contention-Friendly, Non-Blocking Skip List

Report English OPEN
Crain , Tyler; Gramoli , Vincent; Raynal , Michel;
(2012)
  • Publisher: HAL CCSD
  • Subject: [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]

This paper presents a new non-blocking skip list algorithm. The algorithm alleviates contention by localizing synchronization at the least contended part of the structure without altering consistency of the implemented abstraction. The key idea lies in decoupling a modi... View more
  • References (16)
    16 references, page 1 of 2

    [1] B. D. Carlstrom, A. McDonald, M. Carbin, C. Kozyrakis, and K. Olukotun. Transactional collection classes. In PPoPP, 2007.

    [2] T. Crain, V. Gramoli, and M. Raynal. A speculation-friendly binary search tree. In PPoPP, 2012.

    [3] D. L. Detlefs, P. A. Martin, M. Moir, and G. L. Steele, Jr. Lock-free reference counting. In PODC, pages 190-199, 2001.

    [4] E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: an exercise in cooperation. Commun. ACM, 21(11):966-975, 1978.

    [5] P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In DISC, 2009.

    [6] M. Fomitchev and E. Ruppert. Lock-free linked lists and skip lists. In PODC, pages 50-59, 2004.

    [7] K. Fraser. Practical lock freedom. PhD thesis, Cambridge University, September 2003.

    [8] T. Harris. A pragmatic implementation of non-blocking linked-lists. In DISC, pages 300-314, 2001.

    [9] M. P. Herlihy and J. M. Wing. Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12:463-492, July 1990.

    [10] D. Lea. Jsr-166 specification request group.

  • Related Organizations (1)
  • Metrics
Share - Bookmark