More Web Proxy on the site http://driver.im/

article

Open access

The derivation of distributed termination detection algorithms from garbage collection schemes

Editor: Andrew W. Appel Authors:

Friedemann MatternAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 15, Issue 1

Pages 1 - 35

https://doi.org/10.1145/151646.151647

Published: 01 January 1993 Publication History

Abstract

It is shown that the termination detection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the termination detection problem are obtained by applying transformations to garbage collection algorithms. The transformation can be applied to collectors of the “mark-and-sweep” type as well as to reference-counting protocol of Lermen and Maurer, the weighted-reference-counting protocol, the local-reference-counting protocol, and Ben-Ari's mark-and-sweep collector into termination detection algorithms. Known termination detection algorithms as well as new variants are obtained.

References

[1]

BEN-Am, M. Algorithms for on-the-fiy garbage collection. ACM Trans. Program. Lang. Syst. 6, i (July 1984), 333-344.

[2]

BEVAN, D.I. An efficient reference counting solution to the distributed garbage collection problem. Paral. Comput. 9, 2 (1989), 179-192.

[3]

CHANDY, K. M., AND LAMPORT, L. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1 (Feb. 1985), 63-75.

[4]

CHANDY, K. M., AND M~SaA, J. How processes learn. Distrib. Comput. 1, 1 (Jan. 1986), 40-52.

[5]

CHANDY, K. M., MISRA, J., AND HAAS, L. M Distributed deadlock detection. ACM Trans. Comput. Syst. 1, 2 (May 1983), 144-156.

[6]

CHARRON-BOsT, B, TEL, G., AND MATTERN, F. Synchronous and asynchronous commumcation in distributed computations. Tech. Rep. LITP 92.77 Univ. Paris 7, Paris, Oct. 1992.

[7]

CHANDRASEtoERAN, S., AND VENKATESAN, S. A message-optimal algorithm for distributed terminatlon detection. J. Paral. Dlstr~b. Comput. 8, 3 (Mar. 1990), 245-252.

[8]

COLLINS, G.E. A method for overlapping and erasure of lists. Commun. ACM 3, 12 (Dec. 1960), 655-657.

[9]

DIJKSTRA, E. W., AND SCHOLTEN, C.S. Termination detection for diffusing computations. Inf. Proc. Lett. 11, 1 (Aug. 1980), 1-4.

[10]

DIJKSTRA, E. W., FEIJEN, W H. J., AND VAN GASTEREN, A. J.M. Derivation of a termination detection algorithm for distributed computations. Inf. Proc. Lett. 16, 5 (June 1983), 217-219.

[11]

IJKSTRA, E. W., LAMPORT, L., MARTIN, A. J., SCHOLTEN, C. S., AND STEFFENS, E. F. M On-the-fiy garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov. 1978), 966-975.

[12]

European Patent Office. Garbage collection in a computer system. European Patent Application no. 86309082.5.

[13]

FRANCEZ, N. Distributed termination. ACM Trans. Prog. Lang. Syst. 2, 1 (Jan. 1980), 42-55.

[14]

GOLDBER6, B. Generational reference counting' A reduced-communication distributed storage reclamation scheme. ACM SIGPLANNot. 24, 7 (July 1989), 313 321.

[15]

IcaIsuGI, Y., AND YONEZAWA, A. Distributed garbage collection usmg group reference counting. Tech. Rep. 90-014, Dept. Information Science, Univ. of Tokyo, 1990.

[16]

LERMEN, C.-W., AND MAURER, D. A protoco} for distributed reference counting. In ACM Conference on Llsp and Functzonal Programming (Cambridge, Ma., Aug. 4-6, 1986). ACM, New York, 1986, pp. 343-354.

[17]

MATTERN, F. Algorithms for distnbuted termination detection. D~strzb. Comput. 2, 3 (1987), 161-175.

[18]

MATTERN, F. Global quiescence detection based on credit distribution and recovery. Inf. Proc. Lett. 30, 4 (Feb. 1989), 195-200.

[19]

MATTERN, F. Efficient distributed snapshots and global virtual time algorithms for non-FIFO systems. Tech. Rep. SFB124-24/90, Kaiserslautern Univ., 1990.

[20]

MATTERN, F., MEI-IL, Il., SCHOONE, A. A., AND TEL, G. Global virtual time approximation with distributed termination detection algorithms. Tech. Rep. RUU-CS-91-32, Dept. of Computer Science, Univ. of Utrecht, 1991.

[21]

McCARTHY, J. Recursive functions of symbolic expressions and their computation by machine Commun. ACM 3, 4 (Apr. 1960), 184 195.

[22]

MISRA, J. Detecting termination of distributed computations usmg markers. In Proceedings of the 2nd ACM Symposium on Princlples of D~str~buted Computmg (Montreal, Quebec, Aug. 17-19, 1992). ACM, New York, 1983, pp. 290-294.

[23]

NATARAJAN, N. A distributed scheme for detecting communication deadlocks. IEEE Trans. Softw. Eng. SE-12, 4 (Apr. 1986), 531-537.

[24]

PIQUER, J. Indirect reference counting: A distributed garbage collection algorithm. In Proceedzngs Parallel Arch~tectures and Languages, Europe. Vol. 1, Lecture Notes ~n Computer Sctence 505, E. H. L. Aarts, J. van Leeuwen, M. Rem, Eds. Sprlnger-Verlag, Berhn, 1991, pp. 150 165.

[25]

RUDALICS, M. Multiprocessor list memory management. Tech. Rep. RISC-88-87 0, Research Inst. for Symbolic Computation, J. Kepler Univ., Linz, Austria, 1988.

[26]

RUDALICS, M. Implementation of distributed reference counts. Tech. Rep. (forthcoming), Research Inst. for Symbohc Computation, J. Kepler Univ., Lmz, Austria, 1990.

[27]

SAMUELSON, P. Should program algorithms be patented? Commun. ACM 33, 8 (Aug. 1990), 23-27.

[28]

SHAVIT, N., AND FRANCEZ, N. A new approach to detection of locally indicative stability. In Proceedings of ICALP 1986. Lecture Notes in Computer Science 226, L. Kott, Ed. Springer- Verlag, Berlin, 1986, pp. 334-358.

[29]

STEELE, G. L. Multiprocessing compactifying garbage collection. Commun. ACM 18, 9 (Sept. 1975), 495 508.

[30]

SCHOONE, A. A., AND TEL, G. Transformation of a termination detection algorithm and }ts assertional correctness proof. Tech. Rep. RUU-CS-88-40, Dept. of Computer Science, Univ. of Utrecht, 1988.

[31]

TEL, G. Distributed infimum approximation. Tech. Rep. RUU-CS-86-12, Dept. of Computer Science, Univ. of Utrecht, 1986.

[32]

TEL, G. Total algorithms. Algo. Rev. 1, (Jan. 1990), 13-42.

[33]

TEL, G., TAN, R. B., AND VAN LEEUWEN, J. The derivation of graph marking algorithms from distributed termination detection protocols. Sci. Comput. Program. 10, 2 (Apr. 1988), 107 137.

[34]

VAN DE S~EPSCHEUT, J. L.A. "Algorithms for on-the-fiy garbage collection" revisited. Inf. Proc. Lett. 24, 4 (Mar. 1987), 211-216.

[35]

WENG, K.-S. An abstract implementation for a generalized datafiow language. Tech. Rep. MIT/LCS/TR-228, Massachusetts Institute of Technology, 1979.

[36]

ATSON, P., AND WATSON, I. AI1 efficient garbage collection scheme for parallel computer architectures. In Proceed~ngs Parallel Arch~tectures and Languages Europe. Vol. 2, Lecture Notes in Computer Science 259, J. W. de Bakker, A. J. Nijman, P. C. Treleaven, Eds. Springer-Verlag, Berlin, 1987, pp. 432-443.

Cited By

Broy M(2024)A Calculus for the Specification, Design, and Verification of Distributed Concurrent SystemsFormal Aspects of Computing10.1145/367208536:3(1-54)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3672085
Brandt SKrishnan HBusch CSharma G(2018)Distributed garbage collection for general graphsACM SIGPLAN Notices10.1145/3299706.321057253:5(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210572
Brandt SKrishnan HBusch CSharma GPayer HSartor J(2018)Distributed garbage collection for general graphsProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210572(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210572
Show More Cited By

Index Terms

Recommendations

Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Garbage collection in LINDACAP
iiWAS '09: Proceedings of the 11th International Conference on Information Integration and Web-based Applications & Services

LINDACAP provides a capability-based coordination for open distributed systems. As open systems are persistent, garbage collection (GC) can be a vital aspect in managing the systems' resources. Garbage collection has been proposed for the standard Linda ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 15, Issue 1

Jan. 1993

208 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/151646

Editor:
Andrew W. Appel
Princeton Univ., Princeton, NJ

Issue’s Table of Contents

Copyright © 1993 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1993

Published in TOPLAS Volume 15, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
732
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)30

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Broy M(2024)A Calculus for the Specification, Design, and Verification of Distributed Concurrent SystemsFormal Aspects of Computing10.1145/367208536:3(1-54)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3672085
Brandt SKrishnan HBusch CSharma G(2018)Distributed garbage collection for general graphsACM SIGPLAN Notices10.1145/3299706.321057253:5(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210572
Brandt SKrishnan HBusch CSharma GPayer HSartor J(2018)Distributed garbage collection for general graphsProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210572(29-44)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210572
Murray DMcSherry FIsard MIsaacs RBarham PAbadi M(2016)Incremental, iterative data processing with timely dataflowCommunications of the ACM10.1145/298355159:10(75-83)Online publication date: 22-Sep-2016
https://dl.acm.org/doi/10.1145/2983551
Boussabbeh MTounsi MKacem AMosbah M(2016)Towards a General Framework for Ensuring and Reusing Proofs of Termination Detection in Distributed Computing2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP)10.1109/PDP.2016.113(504-511)Online publication date: Feb-2016
https://doi.org/10.1109/PDP.2016.113
Raynal MRaynal M(2013)Distributed Termination DetectionDistributed Algorithms for Message-Passing Systems10.1007/978-3-642-38123-2_14(367-399)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38123-2_14
Shankar AShankar A(2012)Programs, Semantics and Effective AtomicityDistributed Programming10.1007/978-1-4614-4881-5_6(141-171)Online publication date: 4-Aug-2012
https://doi.org/10.1007/978-1-4614-4881-5_6
Shankar AShankar A(2012)Termination Detection for Diffusing ComputationsDistributed Programming10.1007/978-1-4614-4881-5_14(255-267)Online publication date: 4-Aug-2012
https://doi.org/10.1007/978-1-4614-4881-5_14
Shankar AShankar A(2012)Channel with Termination Detection ServiceDistributed Programming10.1007/978-1-4614-4881-5_13(249-253)Online publication date: 4-Aug-2012
https://doi.org/10.1007/978-1-4614-4881-5_13
Shankar AShankar A(2012)IntroductionDistributed Programming10.1007/978-1-4614-4881-5_1(1-39)Online publication date: 4-Aug-2012
https://doi.org/10.1007/978-1-4614-4881-5_1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents