On disjoint-access parallel transactional memories

Participant: Eleftherios Kosmas

Home Institution:
Foundation for Research and Technology - Hellas (FORTH) Institute of Computer Science (ICS)

Home Country: Greece

Host: Prof. Alessia Milani

Host Institution: Laboratoire Bordelais de Recherche en Informatique, University of Bourdeaux

Host Country: France

Start Date:
2012-09-01

End Date: 2012-09-30

Description:
The goal of this scientific mission is to discover whether our previous impossibility result holds for weaker definitions of disjoint-access parallelism, and if this is so, to find different ways to overcome it. These two goals where partially covered during the first visit of Alessia Milani to FORTH, in June 2012, where we had some preliminary ideas on both directions.
More specifically, we tried to extend the impossibility result by considering a weaker definition of disjoint-access parallelism, called partial disjoint-access parallelism. Intuitively, partial disjoint-access parallelism allows two processes executing a TM algorithm to interfere with each other on some specific set of base objects (e.g., on a single timestamp object), even when they operate on different parts of the implemented object. Then, we tried to prove that there is no TM algorithm that ensures both partial disjoint-access parallelism and wait-freedom. Although we have not completed this proof yet, we have a much better understanding of this proof’s subtleties.
Recall that the algorithm, DAP-UC, ensures disjoint-access parallelism and wait- freedom, when applied to objects that have a bound on the number of data items accessed by each operation they support. During the first visit, we designed a new algorithm, called PDAP-UC, that ensures partially disjoint-access parallel and wait-freedom, when applied to any object with bounded number of entry points. Intuitively, an entry point is a data item that is accessed first by an operation of the object.
During the second visit, we first introduced a new disjoint-access parallel property called transitive disjoint-access parallelism, or tdap. Intuitively, this property allows two transactions to contend on some
base object even if they operate on different parts of the implemented object, when their execution intervals overlap with other transactions which are allowed to contend under (our original definition of) disjoint-access parallelism. Since, this property is stronger than disjoint-access parallelism, our previous result is applied; hence, it follows that no TM algorithm is tdap and wait-free for unbounded objects. Therefore, we defined the partially tdap property, which is similar with partial disjoint-access parallelism except that disjoint-access parallelism is replaced with tdap.
Then, we designed a new algorithm, called PtDAP-UC, that is partially tdap and wait-free, for unbounded objects with unbounded entry points.

Report: here