Distributed task and memory management

ABSTRACT

A model of distributed graph reduction is described that has features common to many distributed computing systems: a program (represented as a graph) is partitioned and dynamically distributed among an arbitrary number of processing elements having only local store, and computation takes place as tasks are propagated between vertices in the graph. Specific problems are addressed that are inherent in a computing model of this sort, including garbage collection, detecting deadlock, deleting tasks, and the dynamic prioritization of tasks. By characterizing these problems in terms of graph connectivity, a decentralized graph-marking algorithm is shown to provide an effective solution. This algorithm is unique in that it allows marking a distributed graph whose connectivity is continually changing.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: K. Mani Chandy , J. Misra, Distributed computation on graphs: shortest path algorithms, Communications of the ACM, v.25 n.11, p.833-837, Nov 1982 [doi>10.1145/358690.358717]
• 3: K. Mani Chandy , Jayadev Misra , Laura M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems (TOCS), v.1 n.2, p.144-156, May 1983 [doi>10.1145/357360.357365]
• 4: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 5: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• 6: Hudak, P. Distributed Graph Marking. Research Report 268, Yale University, January, 1983.
• 7: Jhon, C.S., Keller, R. Analysis of unbounded token-flow graphs and realization of unbounded token-flow graph by bounded token-flow graphs. AMPS Technical Memorandum 8, University of Utah, April, 1982.
• 8: J. R. Kennaway , M. R. Sleep, Expressions as processes, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.21-28, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802131]
• 9: Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582155]
• 10: Jayadev Misra , K. M. Chandy, A Distributed Graph Algorithm: Knot Detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.678-686, Oct. 1982 [doi>10.1145/69622.357190]
• 11: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 12: Turner, D.A. A new implementation technique for applicative languages. Software-Practice and Experience 9:31-49, 1970.
• 13: William W. Wadge, An Extensional Treatment of Dataflow Deadlock, Proceedings of the International Sympoisum on Semantics of Concurrent Computation, p.285-299, July 02-04, 1979

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Deadlocks
      D.4.2 Storage Management

General Terms:
Algorithms, Management, Theory