On the interconnection of causal memory systems

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: Sarita Vikram Adve, Designing memory consistency models for shared-memory multiprocessors, University of Wisconsin at Madison, Madison, WI, 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: Hagit Attiya , Jennifer L. Welch, Sequential consistency versus linearizability, ACM Transactions on Computer Systems (TOCS), v.12 n.2, p.91-122, May 1994 [doi>10.1145/176575.176576]
• 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: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 7: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 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: Ravi Prakash , Michel Raynal , Mukesh Singhal, An adaptive causal ordering algorithm suited to mobile computing environments, Journal of Parallel and Distributed Computing, v.41 n.2, p.190-204, March 15, 1997 [doi>10.1006/jpdc.1996.1300 ]
• 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: Himanshu Shekhar Sinha, Mermera: non-coherent distributed shared memory for parallel computing, Boston University, Boston, MA, 1993

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Experimentation, Theory, Verification