Click here for full text:
Debugging of Distributed Computations via Memory- Efficient Enumeration of Global States
Andrzejak, Artur; Fukuda, Komei
Keyword(s): distributed computations; debugging; global states
Abstract: 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.
Back to Index