Working Groups‎ > ‎

WG2: Theoretical foundations & Algorithms

WG Leader: Dr. Tim Harris


Unlike database transactions, in a TM transactions do not execute in a sand-boxed environment. This exposes TM transactions to hazardous execution scenarios that would not be filtered out by the safety and liveness properties normally ensured in a DBMS environment. 

On the safety side, for instance, if, in a TM, a transaction observes an inconsistent system it may generate unexpected memory access violations or arithmetic exceptions, causing the failure of the whole application, or get trapped in infinite loops, never reaching the commit phase. This kind of phenomena is absent in a database system where transactions observing stale state can be eventually aborted without harmful side effects (except of course from a performance perspective). Further, in a TM, application's state can be concurrently accessed by both transactional and non-transactional code, a scenario clearly not modeled by classical database serialization theory. On the progress side, lock-based concurrency control schemes are extremely popular in DBMSs, where deadlocks can be lazily detected incurring simply in a performance penalty; in a TM system, conversely, lock-based solutions are often deemed unacceptable as the consequences of deadlocks (e.g. involving interrupt handlers) may lead to a halt of the whole system. 

This WG will carry out foundational research aimed, firstly, at precisely formalizing the correctness criteria that TM implementations should provide. Secondly, based on such formalization, the WG will work on the design, verification and performance analysis of TM algorithms, considering both the scenarios of deployment on a single cache coherent shared memory system and over a set of distributed, shared-nothing nodes. The performance analysis carried out within this WG will be of a twofold nature. From a theoretical perspective, they will aim at establishing fundamental complexity and optimality results, shedding light on the inherent costs of the various trade-offs in the TM's design space. These theoretical results will be complemented by performance evaluation studies of software based implementations using, whenever possible, the benchmarking applications that will be produced by WG5.