Distributed Task and Memory Management

Authors:

Paul Hudak

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.

Bibtex:

 @InProceedings{huda83c
    ,key={hudak}
    ,author={Hudak, P.}
    ,title={Distributed Task and Memory Management}
    ,booktitle={Proceedings of Symposium on Principles of Distributed Computing}
    ,organization={ACM}
    ,year=1983
    ,editors={Lynch, N.A., et al.}
    ,month=Aug
    ,pages={277-289}
    } 

Links:

DistTaskMgmt-PODC83.pdf