Debugging Distributed Computations by Reverse Search

A. Andrzejak (Germany) and K. Fukuda (Canada)


Distributed Computations, Global States, Debugging, Reverse Search


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. 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, Marzullo and Neiger [8, 14]. The basis for these algorithms is Reverse Search [2], a paradigm successfully applied for enumeration of a variety of geometric objects.

Important Links:

Go Back