Debugging of Distributed Computations via Memory- Efficient Enumeration of Global

Andrzejak, Artur ; Fukuda, Komei

HP Development Company

关键词: distributed computations;    debugging;    global states;   

RP-ID  :  HPL-2002-31

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We develop a memory-efficient off-line algorithm for the enumeration of global states of a distributed computation. The algorithm allows the parameterization of its memory requirements against the running time. In the extreme case, only one global state of a distributed computation must be held in the memory of the enumerating system at a time. This is particularly useful for debugging of memory-intensive parallel computations, e.g. in image processing or data warehousing. We also show how to apply our technique to evaluate in a memory-efficient way the predicate Definitely (Φ) defined by Cooper and Marzullo. The basis for these algorithms is Reverse Search, a paradigm successfully applied for enumeration of a variety of geometric objects. 11 Pages