Brief Announcement: Queuing or Priority Queuing? On the Design of Cache-Coherence Protocols for Distributed Transactional Memory *

摘要

In distributed transactional memory (TM) systems, both the management and consistency of a distributed transactional object are ensured by a cache-coherence protocol. We formalize two classes of cache-coherence protocols: distributed queuing cache-coherence (DQC) protocols and distributed priority queuing cache-coherence (DPQC) protocols, both of which can be implemented based on a given distributed queuing protocol. We analyze the two classes of protocols for a set of dynamically generated transactions and compare their time complexities against that of an optimal offline clairvoyant algorithm. We show that a DQC protocol Is O(N Log Dδ)-competitive and a DPQC protocol is O(log Dδ)-coinpetitive for a set of N transactions, where Dδ is the normalized maximum communication latency provided by the underlying distributed queuing protocol.