Distributed data structures in Linda

ABSTRACT

A <i>distributed data structure</i> is a data structure that can be manipulated by many parallel processes simultaneously. Distributed data structures are the natural complement to parallel program structures, where a <i>parallel program</i> (for our purposes) is one that is made up of many simultaneously active, communicating processes. Distributed data structures are impossible in most parallel programming languages, but they are supported in the parallel language Linda and they are central to Linda programming style. We outline Linda, then discuss some distributed data structures that have arisen in Linda programming experiments to date. Our intent is neither to discuss the design of the Linda system nor the performance of Linda programs, though we do comment on both topics; we are concerned instead with a few of the simpler and more basic techniques made possible by a language model that, we argue, is subtly but fundamentally different in its implications from most others.This material is based upon work supported by the National Science Foundation under Grant No. MCS-8303905. Jerry Leichter is supported by a Digital Equipment Corporation Graduate Engineering Education Program fellowship.

REFERENCES

• 1: {Ahu83} S. Ahuja. "S/Net: a high-speed interconnect for multiple computers." <i>IEEE Selected Areas in Communication.</i> (Nov. 1983):751--756.
• 2: Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
• 3: Nicholas Carriero , David Gelernter, The S/Net's Linda kernel (extended abstract), Proceedings of the tenth ACM symposium on Operating systems principles, p.160, December 1985, Orcas Island, Washington, United States
• 4: David R. Cheriton , Willy Zwaenepoel, The distributed V kernel and its performance for diskless workstations, Proceedings of the ninth ACM symposium on Operating systems principles, p.129-140, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 5: David R. Cheriton , Willy Zwaenepoel, Distributed process groups in the V Kernel, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.77-107, May 1985 [doi>10.1145/214438.214439]
• 6: {Deu84} J. T. Deutsch and A. R. Newton. "MSPLICE: A multiprocessor-based circuit simulator," in <i>Proc. 1984 Intl. Conf. Parallel Processing,</i> (Aug. 1984):207--214.
• 7: {Gel84} D. Gelernter. "Dynamic global name spaces on network computers," in <i>Proc. Intl. Conf. Parallel Processing,</i> (Aug. 1984).
• 8: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 9: {Gel85a} D. Gelernter. "Symmetric Programming Languages." Yale Univ. Dept. Comp. Sci. Tech. Report yaleu/dcs/rr#253. Aug. 1985.
• 10: {GCCC85} D. Gelernter. N. Carriero. S. Chandran and S. Chang. "Parallel programming in Linda," in <i>Proc. Int. Conf. Parallel Processing.</i> (Aug. 1985) (to appear).
• 11: Richard P. Gabriel , John McCarthy, Queue-based multi-processing LISP, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.25-44, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802019]
• 12: {Gott83} A. Gottlieb, R. Grishman, C. P. Kruksal, K. P. McAuliffe, L. Rudolph and M. Snir, "The NYU Ultracomputer -- Designing an MIMD Shared Memory Parallel Computer." <i>IEEE Trans. Comput.</i> C-32, 2(1983):175--189.
• 13: {Leic85} J. Leichter, "Implementing the Unimplementable -- Algorithms for Linda's Tuple Space". Yale University Dept. Comp. Sci. internal report.
• 14: {Mull84} R. Mullin. E. Nemeth and N. Weidenhofer. "Will public key crypto systems live up to their expectations? HEP Implementation of the discrete log codebreaker." in <i>Proc. 1984 Intl. Conf. Parallel Processing,</i> (Aug. 1984):193--195.