skip to main content
10.1145/343477.343540acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article
Free access

On the interconnection of causal memory systems

Published: 16 July 2000 Publication History

Abstract

A large amount of work has been invested in devising algorithms to implement distributed shared memory (DSM) systems under different consistency models. However, to our knowledge, the possibility of interconnecting DSM systems with simple protocols and the consistency of the resulting system has never been studied. With this paper, we start a series of works on the properties of the interconnection of DSM systems, which tries to fill this void.
In this paper, we look at the interconnection of propagation-based causal DSM systems. We present extremely simple algorithms to interconnect two such systems (possibly implemented with different algorithms), that only require the existence of a bidirectional reliable FIFO channel connecting one process from each system. We show that the resulting DSM system is also causal. This result can be generalized to interconnect any number of DSM propagation-based causal systems.

References

[1]
S. Adve. Designing Memory Consistency Models for Shared.Memory Multiprocessors. PhD thesis, University of Wisconsin-Madison, 1993.
[2]
M. Ahamad, G. Neiger, J. Burns, P. Kohli, and P. Hutto. Causal memory: Definitions, implementation and programming. Distributed Computing, 9(1):37-49, August 1995.
[3]
H. Attiya and J. Welch. Sequential consistency versus linearizability. A CM Transactions on Computer Systems, 12(2):91-122, 1994.
[4]
V. Cholvi. Specification of the behavior of memory operations in distributed systems. Parallel Processing Letters, 8(4):589--598, December 1998.
[5]
J. Goodman. Cache consistency and sequential consistency. Technical Report 61, IEEE Scalable Coherence Interface Working Group, March 1989.
[6]
M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. A CM Transactions on Programming Languages and Systems, 12(3):463--492, July 1990.
[7]
L. Lamport. Time, clocks and the ordering of events in a distributed system. Communications of the A CM, 21(7):558-565, July 1991.
[8]
R. Lipton and J. Sandberg. PRAM: A scalable sh~ed memory. Technical Report CS-TR-180-88, Princeton University, Department of Computer Science, September 1988.
[9]
R. Prakash, M. Raynal, and M. Singhal. An adaptive causal ordering algorithm suited to mobile computing environments. Journal of Parallel and Distributed Computing, 41:190-204, 1997.
[10]
M. Raynal and M. Ahamad. Exploiting write semantics in implementing partially replicated causal objects. In Proceedings of the 6th EUI~OMICRO Conference on Parallel and Distributed Computing, pages 157-163, Feb 1998.
[11]
A. Singh. Bounded timestamps in process networks. Parallel Processing Letters, 6(2):259-264, 1996.
[12]
H. Sinha. Mermera: Non.Coherent Distributed Shared Memory for Parallel Computing. PhD thesis, Computer Science Department, Boston University, April 1993.

Cited By

View all
  • (2016)Scalability approaches for causal multicastComputing10.1007/s00607-015-0479-098:9(923-947)Online publication date: 1-Sep-2016
  • (2005)Mixed Consistency ModelProceedings of the 25th IEEE International Conference on Distributed Computing Systems10.1109/ICDCS.2005.49(209-218)Online publication date: 6-Jun-2005
  • (2005)Plausible clocks with bounded inaccuracyProceedings of the 19th international conference on Distributed Computing10.1007/11561927_17(214-228)Online publication date: 26-Sep-2005
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '00: Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing
July 2000
344 pages
ISBN:1581131836
DOI:10.1145/343477
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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 2000

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

PODC00
Sponsor:

Acceptance Rates

PODC '00 Paper Acceptance Rate 32 of 117 submissions, 27%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)113
  • Downloads (Last 6 weeks)51
Reflects downloads up to 14 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Scalability approaches for causal multicastComputing10.1007/s00607-015-0479-098:9(923-947)Online publication date: 1-Sep-2016
  • (2005)Mixed Consistency ModelProceedings of the 25th IEEE International Conference on Distributed Computing Systems10.1109/ICDCS.2005.49(209-218)Online publication date: 6-Jun-2005
  • (2005)Plausible clocks with bounded inaccuracyProceedings of the 19th international conference on Distributed Computing10.1007/11561927_17(214-228)Online publication date: 26-Sep-2005
  • (2004)Adaptive plausible clocks24th International Conference on Distributed Computing Systems, 2004. Proceedings.10.1109/ICDCS.2004.1281571(86-93)Online publication date: 2004
  • (2003)On the Locality of Consistency ConditionsDistributed Computing10.1007/978-3-540-39989-6_7(92-105)Online publication date: 2003
  • (2002)On the Stability of Compositions of Universally Stable, Greedy Contention-Resolution ProtocolsDistributed Computing10.1007/3-540-36108-1_6(88-102)Online publication date: 24-Oct-2002

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media