Optimistic concurrency for clusters via speculative locking

Abstract

Transactional memory and speculative locking are optimistic concurrency control mechanisms, whose goal is to enable highly concurrent execution while reducing the programming effort. The same basic idea lies in the heart of both methods: optimistically execute a critical code segment, determine whether there have been data conflicts and roll back in case validation fails. Transactional memory is widely considered to have advantages over lock-based synchronization on shared memory multiprocessors. Several recent works suggest employment of transactional memory in a distributed environment. However, being derived from traditional shared-memory design space, these schemes seem to be not "optimistic" enough for this setting. Each thread must validate the current transaction before proceeding to the next. Hence, blocking remote requests whose purpose is to detect/avoid data conflicts are placed on the critical path and thus delay execution. In this paper, we investigate whether in light of the above shortcomings speculative locking can be a suitable alternative for transactional memory in a distributed environment. We present a novel distributed speculative locking scheme and compare its properties to the existing distributed transactional memory protocols. Despite the conceptual similarity to transactional memory, the distributed implementation of speculative locking manages to overlap communication with computation. It allows a thread to speculatively acquire multiple locks simultaneously, which is analogous to executing one transaction before validating the previous.