Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free
 
conference paper

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

David, Tudor Alexandru  
•
Guerraoui, Rachid  
2016
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
28th ACM Symposium on Parallelism in Algorithms and Architectures

We argue that there is virtually no practical situation in which one should seek a "theoretically wait-free" algorithm at the expense of a state-of-the-art blocking algorithm in the case of search data structures: blocking algorithms are simple, fast, and can be made "practically wait-free". We draw this conclusion based on the most exhaustive study of blocking search data structures to date. We consider (a) different search data structures of different sizes, (b) numerous uniform and non-uniform workloads, representative of a wide range of practical scenarios, with different percentages of update operations, (c) with and without delayed threads, (d) on different hardware technologies, including processors providing HTM instructions. We explain our claim that blocking search data structures are practically wait-free through an analogy with the birthday paradox, revealing that, in state-of-the-art algorithms implementing such data structures, the probability of conflicts is extremely small. When conflicts occur as a result of context switches and interrupts, we show that HTM-based locks enable blocking algorithms to cope with them

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

p337-david.pdf

Type

Publisher's Version

cris-layout.advanced-attachment.oaire.version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

1.07 MB

Format

Adobe PDF

Checksum (MD5)

70087f4309b160f010856d0805ea661c

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés