D2STM: Dependable Distributed Software Transactional Memory
M. Couceiro, P. Romano, N. Carvalho, L. Rodrigues.
Selected sections of this report were published in the Proceedings of
the 15th Pacific Rim International Symposium on Dependable Computing
(PRDC 09), Shanghai, China, November 16-18, 2009.
Abstract
Software Transactional Memory (STM) systems have emerged as a
powerful paradigm to develop concurrent applications. At current
date, however, the problem of how to build distributed and
replicated STMs to enhance both dependability and performance
is still largely unexplored. This paper fills this gap by presenting
D2STM, a replicated STM that makes use of the computing resources
available at multiple nodes of a distributed system. The consistency
of the replicated STM is ensured in a transparent manner, even in
the presence of failures. In D2STM transactions are autonomously
processed on each node, avoiding any replica inter-communication
during transaction execution, and without incurring in deadlocks.
Strong consistency is enforced at
transaction commit time by a non-blocking distributed certification
scheme, which we name BFC (Bloom Filter Certification). BFC
exploits a novel Bloom Filter-based encoding mechanism that permits
to significantly reduce the overheads of replica coordination
at the cost of a user tunable increase in the probability of transaction abort.
Through an extensive experimental study based on standard STM benchmarks
we show that the BFC scheme permits to achieve remarkable performance gains even
for negligible (e.g. 1%) increases of the transaction abort rate.
Also available extended report (pdf)
Luís Rodrigues