short-paper

OPCAM: Optimal Algorithms Implementing Causal Memories in Shared Memory Systems

Authors:

Ajay D. Kshemkalyani,

Ta-yuan HsuAuthors Info & Claims

ICDCN '15: Proceedings of the 16th International Conference on Distributed Computing and Networking

Article No.: 16, Pages 1 - 4

https://doi.org/10.1145/2684464.2684483

Published: 04 January 2015 Publication History

Abstract

Data replication is commonly used for fault tolerance in reliable distributed systems. In this paper, we propose three optimal protocols for causal consistency in distributed shared memory systems. Our proposed optimal protocols are designed for partial replication across the distributed shared memory. Complete replication is a special case of our protocols and we also give the optimal implementation of causal consistency for the complete replication case. Algorithm Full-Track is optimal in the sense that it can update the local copy as soon as possible while respecting causal consistency. Algorithm Opt-Track is further optimal in the sense that the size of the local logs maintained and the amount of control information piggybacked on the update messages is minimal. Algorithm Opt-Track-CRP is a special case of algorithm Opt-Track for the full replication case. It is highly scalable, and significantly more efficient than the Baldoni et al. protocol for the complete replication case.

References

[1]

M. Ahamad, G. Neiger, J. Burns, P. Kohli, and P. Hutto. Causal memory: definitions, implementation and programming. Distributed Computing, 9, 1, pages 37--49, 1995.

Digital Library

[2]

R. Baldoni, A. Milani, and S. Piergiovanni. Optimal propagation-based protocols implementing causal memories. Distributed Computing, 18, 6, pages 461--474, 2006.

Digital Library

[3]

N. Belaramani, M. Dahlin, L. Gao, A. Venkataramani, P. Yalagandula, and J. Zheng. Practi replication. In NSDI, 2006.

Digital Library

[4]

P. Bernstein and S. Das. Rethinking eventual consistency. Proc. of the 2013 ACM SIGMOD International Conf. on Management of Data, 2013.

Digital Library

[5]

P. Chandra, P. Gambhire, and A. D. Kshemkalyani. Performance of the optimal causal multicast algorithm: A statistical analysis. IEEE Transactions on Parallel and Distributed Systems, 15(1), pages 40--52, January 2004.

Digital Library

[6]

P. Chandra and A. D. Kshemkalyani. Causal multicast in mobile networks. Proc. of the 12th IEEE/ACM Symposium on Modelling, Analysis, and Simulation of Computer and Communication Systems, pages 213--220, 2004.

Digital Library

[7]

G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. Proc. of the 19th ACM SOSP, pages 205--220, 2007.

Digital Library

[8]

S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, 2002.

Digital Library

[9]

A. Kshemkalyani and M. Singhal. An optimal algorithm for generalized causal message ordering. Proc. of the 15th ACM Symposium on Principles of Distributed Computing (PODC), page 87, 1996.

Digital Library

[10]

A. Kshemkalyani and M. Singhal. Necessary and sufficient conditions on information for causal message ordering and their optimal implementation. Distributed Computing, 11, 2, pages 91--111, 1998.

Digital Library

[11]

A. Kshemkalyani and M. Singhal. Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, 2008.

Digital Library

[12]

W. Lloyd, M. Freedman, M. Kaminsky, and D. Andersen. Don't settle for eventual: Scalable causal consistency for wide-area storage with COPS. Proc. of the 23rd ACM SOSP, pages 401--416, 2011.

Digital Library

[13]

P. Mahajan, L. Alvisi, and M. Dahlin. Consistency, availability, and convergence. Tech. Rep. TR-11-22, Univ. Texas at Austin, Dept. Comp. Sci., 2011.

[14]

K. Petersen, M. Spreitzer, D. Terry, M. Theimer, and A. Demers. Flexible pdate propagation for weakly consistent replication. In SOSP, 1997.

Digital Library

[15]

M. Raynal, A. Schiper, and S. Toueg. The causal ordering abstraction and a simple way to implement it. Information Processing Letters, 39, 6, pages 343--350, 1991.

Digital Library

[16]

M. Shen, A. Kshemkalyani, and T. Hsu. OPCAM: Optimal algorithms implementing causal memories in shared memory systems. Tech. Rep., Univ. Illinois at Chicago, Dept. Comp. Sci., 2014.

Cited By

Mahmood TNarayanan SRao SVijaykumar TThottethodi M(2021)Karma: Cost-Effective Geo-Replicated Cloud Storage with Dynamic Enforcement of Causal ConsistencyIEEE Transactions on Cloud Computing10.1109/TCC.2018.28421849:1(197-211)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TCC.2018.2842184
Tseng LWang ZZhao Y(2019)Resilient Distributed Causal Memory in Client-Server Model2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC47002.2019.00035(95-9509)Online publication date: Dec-2019
https://doi.org/10.1109/PRDC47002.2019.00035
Hsu TKshemkalyani A(2018)Value the Recent PastIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.274017429:1(212-225)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1109/TPDS.2017.2740174
Show More Cited By

Index Terms

OPCAM: Optimal Algorithms Implementing Causal Memories in Shared Memory Systems
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Approximate causal consistency for partially replicated geo-replicated cloud storage
NDM '15: Proceedings of the Fifth International Workshop on Network-Aware Data Management

In geo-replicated systems and the cloud, data replication provides fault tolerance and low latency. Causal consistency in such systems is an interesting consistency model. Most existing works assume the data is fully replicated because this greatly ...
Performance of Approximate Causal Consistency for Partially Replicated Systems
ARMS-CC'16: Proceedings of the Third International Workshop on Adaptive Resource Management and Scheduling for Cloud Computing

Causal consistency is one of the widely used consistency models in wide-area replicated systems due to highly scalable semantics. Partial replication is a replication mechanism that emphasizes a better network capacity utilization. However, it has a ...
Causal Consistency for Geo-Replicated Cloud Storage under Partial Replication
IPDPSW '15: Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop

Data replication is a common technique used for fault-tolerance in reliable distributed systems. In geo-replicated systems and the cloud, it additionally provides low latency. Recently, causal consistency in such systems has received much attention. ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICDCN '15: Proceedings of the 16th International Conference on Distributed Computing and Networking

January 2015

360 pages

ISBN:9781450329286

DOI:10.1145/2684464

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 January 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper
Research
Refereed limited

Conference

ICDCN '15

ICDCN '15: International Conference on Distributed Computing and Networking

January 4 - 7, 2015

Goa, India

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mahmood TNarayanan SRao SVijaykumar TThottethodi M(2021)Karma: Cost-Effective Geo-Replicated Cloud Storage with Dynamic Enforcement of Causal ConsistencyIEEE Transactions on Cloud Computing10.1109/TCC.2018.28421849:1(197-211)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TCC.2018.2842184
Tseng LWang ZZhao Y(2019)Resilient Distributed Causal Memory in Client-Server Model2019 IEEE 24th Pacific Rim International Symposium on Dependable Computing (PRDC)10.1109/PRDC47002.2019.00035(95-9509)Online publication date: Dec-2019
https://doi.org/10.1109/PRDC47002.2019.00035
Hsu TKshemkalyani A(2018)Value the Recent PastIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2017.274017429:1(212-225)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1109/TPDS.2017.2740174
Hsu TKshemkalyani AShen M(2018)Causal consistency algorithms for partially replicated and fully replicated systemsFuture Generation Computer Systems10.1016/j.future.2017.04.04486:C(1118-1133)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1016/j.future.2017.04.044
Hsu TKshemkalyani A(2016)Performance of Approximate Causal Consistency for Partially Replicated SystemsProceedings of the Third International Workshop on Adaptive Resource Management and Scheduling for Cloud Computing10.1145/2962564.2962572(7-13)Online publication date: 25-Jul-2016
https://dl.acm.org/doi/10.1145/2962564.2962572
Kshemkalyani AHsu TBalman MByna STierney B(2015)Approximate causal consistency for partially replicated geo-replicated cloud storageProceedings of the Fifth International Workshop on Network-Aware Data Management10.1145/2832099.2832102(1-8)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2832099.2832102
Shen MKshemkalyani AHsu T(2015)Causal Consistency for Geo-Replicated Cloud Storage under Partial ReplicationProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop10.1109/IPDPSW.2015.68(509-518)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPSW.2015.68

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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents