Alan Dix > 1994

Download full technical report (PDF, 730K)

Full reference:

I. Toyn and A. J. Dix (1994).
Efficient Binary Transfer of Pointer Structures.
Software Practice and Experience, 24(11): 1001-1023.
DOI: 10.1002/spe.4380241103.
http://alandix.com/academic/papers/SPE-binary-transfer-1994/

Keywords Pointer structure, Lazy transfer, Distributed system, Inter-process communication, Remote procedure call, Cadiz

abstract

This paper presents a pair of algorithms for output and input of pointer structures in binary format. Both algorithms operate in linear space and time. They have been inspired by copying garbage collection algorithms, and make similar assumptions about the representations of pointer structures.

In real programs, the transfer of entire pointer structures is often inappropriate. The algorithms are extended to transfer partitions of a pointer structure lazily: the receiver requests partitions when it needs them.

A remote procedure call mechanism is presented that uses the binary transfer algorithms for communicating arguments and results. A use of this as an enabling mechanism in the implementation of a software engineering environment is discussed.

references

1. 1. R. R. Fenichel and J. C. Yochelson, 'A LISP garbage-collector for virtual-memory computer systems', Communications of the ACM 12(11), 611–612 (1969).
2. P. R. Wilson, 'Uniprocessor garbage collection techniques', in Y. Bekkers and J. Cohen (eds), International Workshop on Memory Management, Springer Verlag Lecture Notes in Computer Science 637, September 1992, pp. 1–42.
3. C. J. Cheney, 'A nonrecursive list compacting algorithm', Communications of the ACM, 13(11), 677– 678 (1970).
4. D. A. Fisher, 'Copying cyclic list structures in linear time using bounded workspace', Communications of the ACM, 18(5), 251–252 (1975).
5. D. W. Clark, 'A fast algorithm for copying list structures', Communications of the ACM, 21(5), 351– 357 (1978).
6. A. S. Tanenbaum, R. van Renesse, H. van Staveren, G. J. Sharp, S. J. Mullender, J. Jansen and G. van Rossum, 'Experiences with the AMOEBA distributed operating system', Communications of the ACM, 33, 46–63 (1990).
7. SUN Microsystems, Network Programming Guide, 1990.
8. S. Wilbur and B. Bacarisse, 'Building distributed systems with remote procedure call', Software Engineering Journal, 2(5), 148–159 (1987).
9. Andrew S. Tanenbaum, Modern Operating Systems, Prentice-Hall Int., 1992.
10. A. D. Birrell and B. J. Nelson, 'Implementing remote procedure calls', ACM Transactions on Computer Systems, 2(1), 39–59 (1984).
11. D. T. Jordan, J. A. McDermid and I. Toyn, 'CADiZ—computer aided design in Z', 5th Oxford Z User Meeting, Springer-Verlag Workshops in Computing, December 1990.
12. D. A. Lamb, 'Sharing intermediate representations: the interface description langauge', CMU-CS-83- 129, Department of Computer Science, Carnegie-Mellon University, May 1983.
13. J. M. Newcomer, 'Efficient binary I/O of IDL objects', ACM SIGPLAN Notices, 22(11), 35–43 (1987).
14. M. Herlihy and B. Liskov, 'A value transmission method for abstract data types', ACM Transactions on Programming Languages and Systems, 4(4), 527–551 (1982).