Location-aware cache-coherence protocols for distributed transactional contention management in metric-space networks

Abstract. Transactional memory is an alternative programming model for managing con-tention in accessing shared in-memory data objects. Distributed transactional memory promises to alleviate diculties with lock-based (distributed) synchronization and object performance bottlenecks in distributed systems. The design of the cache-coherence protocol is critical to the performance of distributed transactional memory systems. We evaluate the performance of a cache-coherence protocol by measuring its worst-case competitive ratio | i.e., the ratio of its makespan to the makespan of the optimal cache-coherence protocol. We establish the upper bound of the competitive ratio and show that it is determined by the worst-case num-ber of abortions, maximum locating stretch, and maximum moving stretch of the protocol | the rst such result. We present the Relay protocol, a novel cache-coherence protocol, which optimizes these values, and evaluate its performance. We show that Relay's competitive ratio is signicantly improved by a factor of O(Ni) for Ni transactions requesting the same object when compared against past distributed queuing protocols.