Disjoint-access parallelism in software transactional memory

Hagit Attiya, Panagiota Fatourou

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

Disjoint-access parallelism captures the requirement that unrelated transactions progress independently, without interference, even if they occur at the same time. That is, an implementation should not cause two transactions, which are unrelated at the high-level, i.e. they access disjoint sets of data items, to simultaneously access the same low-level shared memory locations. This chapter will formalize this notion and will discuss if and when STM can achieve disjointaccess parallelism, by presenting impossibility results and discussing some of the disjoint-access parallel STM implementations. For example, no dynamic STM can be disjoint-access parallel, if it ensures wait-freedom for read-only transactions and a weak liveness property, known as minimal progress, for update transactions. In fact, even if transactions are static, STM implementations cannot be disjoint-access parallel, when read-only transactions must be wait-free and invisible. These impossibility results hold even when only snapshot isolation is required for the STM, and not stronger conditions like opacity or strict serializability. The second of these impossibility results holds for serializable STM as well.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)72-97
عدد الصفحات26
دوريةLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت8913
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Disjoint-access parallelism in software transactional memory'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا