ملخص
A contention-sensitive data structure is a concurrent data structure in which the overhead introduced by locking is eliminated in common cases, when there is no contention, or when processes with non-interfering operations access it concurrently. When a process invokes an operation on a contention-sensitive data structure, in the absence of contention or interference, the process must be able to complete its operation in a small number of steps and without using locks. Using locks is permitted only when there is interference. We formally define the notion of contention-sensitive data structures, propose four general transformations that facilitate devising such data structures, and illustrate the benefits of the approach by implementing a contention-sensitive consensus algorithm, a contention-sensitive double-ended queue data structure, and a contention-sensitive election algorithm.
اللغة الأصلية | الإنجليزيّة |
---|---|
الصفحات (من إلى) | 41-55 |
عدد الصفحات | 15 |
دورية | Theoretical Computer Science |
مستوى الصوت | 677 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 16 مايو 2017 |
منشور خارجيًا | نعم |
ملاحظة ببليوغرافية
Publisher Copyright:© 2017 Elsevier B.V.