Enumerating Global States of a Distributed Computation

V.K. Garg (USA)


Global Predicate Detection, Combinatorial Enumeration,Lattices, Ideals


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:

Go Back