Enumerating Global States of a Distributed Computation

V.K. Garg (USA)

Keywords

Global Predicate Detection, Combinatorial Enumeration,Lattices, Ideals

Abstract

Global predicate detection is a fundamental problem in distributed computing in the areas of distributed debug ging and software fault-tolerance. It requires searching the global state lattice of a computation to determine if any consistent global state satisfies the given predicate. We give an efficient algorithm that perform the lex traversal of the lattice. We also give a space efficient algorithm for the breadth-first-search (BFS) traversal.

Important Links:

• DOI:
• From Proceeding (392) Parallel and Distributed Computing and Systems - 2003

Go Back