Cited By
View all- Busch CChlebus BKowalski DPoudel P(2023)Stable Scheduling in Transactional MemoryAlgorithms and Complexity10.1007/978-3-031-30448-4_13(172-186)Online publication date: 25-Apr-2023
Brief announcement: queuing or priority queuing? on the design of cache-coherence protocols for distributed transactional memory
Authors: 
Bo Zhang, 
Binoy RavindranAuthors Info & Claims
Bo Zhang, Binoy RavindranAuthors Info & ClaimsAbstract
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(Nlog Dδ)-competitive and a DPQC protocol is O(log Dδ)-competitive for a set of N transactions, where Dδ is the normalized maximum communication latency provided by the underlying distributed queuing protocol.
References
[1]
H. Attiya, L. Epstein, H. Shachnai, and T. Tamir. Transactional contention management as a non-clairvoyant scheduling problem. In PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 308--315, New York, NY, USA, 2006. ACM.
[2]
R. Guerraoui, M. Herlihy, and B. Pochon. Toward a theory of transactional contention managers. In PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 258--264, New York, NY, USA, 2005. ACM.
[3]
M. Herlihy and Y. Sun. Distributed transactional memory for metric-space networks. Distributed Computing, 20(3):195--208, 2007.
[4]
F. Kuhn and R. Wattenhofer. Dynamic analysis of the arrow distributed protocol. In SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 294--301, New York, NY, USA, 2004. ACM.
[5]
B. Zhang and B. Ravindran. Location-aware cache-coherence protocols for distributed transactional contention management in metric-space networks. In SRDS '09: Proceedings of the 2009 28th IEEE International Symposium on Reliable Distributed Systems, pages 268--277, Washington, DC, USA, 2009. IEEE Computer Society.
[6]
B. Zhang and B. Ravindran. Queuing or priority queuing? On the design of cache-coherence protocols for distributed transactional memory. Technical report, Virginia Tech, 2010. http://www.real-time.ece.vt.edu/dpqtm_TR.pdf.
Index Terms
- Brief announcement: queuing or priority queuing? on the design of cache-coherence protocols for distributed transactional memory
Recommendations
Brief Announcement: Asynchronous Secure Distributed Computing with Transferrable Non-equivocation Revisited
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed ComputingIn this paper, we consider two fundamental problems in secure distributed computing, namely Asynchronous Byzantine Agreement (ABA) and Asynchronous Secure Multi-party Computation (ASMPC). Our focus is on the honest majority setting, involving a set of n ...
Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computingFair exchange is one of the most fundamental problems in secure distributed computation. Alice has something that Bob wants, and Bob has something that Alice wants. A fair exchange protocol would guarantee that, even if one of them maliciously deviates ...
Brief announcement: on enhancing concurrency in distributed transactional memory
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computingDistributed transactional memory (TM) models based on globally-consistent contention management policies may abort many transactions that could potentially commit without violating correctness. To reduce unnecessary aborts and increase concurrency, we ...
Comments
Information & Contributors
Information
Published In
July 2010
494 pages
Copyright © 2010 Copyright is held by the author/owner(s).
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 July 2010
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 126Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 06 Nov 2024
Other Metrics
Citations
Cited By
View all- Busch CChlebus BKowalski DPoudel P(2023)Stable Scheduling in Transactional MemoryAlgorithms and Complexity10.1007/978-3-031-30448-4_13(172-186)Online publication date: 25-Apr-2023
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in