Global predicate detection is a fundamental problem in distributed
computing in the areas of distributed debugging and 
software fault-tolerance.
It requires searching the global state lattice of a computation
to determine if any consistent global state (CGS) satisfies the given predicate.
Alagar and Venkatesan's algorithm performs
the depth-first-search (DFS) traversal of the lattice and
requires $O(nM)$ time and $O(nE)$ space where 
where $n$ is the number of processes, $M$ is the number of 
consistent global states and $E$ is the number of events in
the computation. In many distributed computing applications,
the breadth-first-search (BFS) traversal and the {\em lexical}
traversal of the lattice are more useful.
We propose a new algorithm
that performs the {\em lexical} traversal of the lattice
with $O(nE)$ space and $O(n^2M)$ time complexity.
Cooper and Marzullo's algorithm performs a
BFS traversal and requires exponential 
{\em space}.
We show that the time complexity of 
the BFS traversal can be reduced by exploiting the distributive 
lattice structure of the global state graph.
Further, we show that the BFS can be performed
in polynomial space by increasing the time complexity.

Enumeration of the CGS lattice in the {\em lexical} and the BFS
order has applications in combinatorial enumeration besides distributed
computing.
We show that the algorithms discussed in the paper can be used to
efficiently enumerate all subsets of $[n]$ (the set $\{1..n\}$), all subsets 
of $[n]$ of size $k$,
all permutations, 
all integer partitions less than a given partition, all
integer partitions of a given number, all $n$-tuples of a 
product space, and many other families of combinatorial objects.

Finally, we discuss detection of global predicate under {\em definitely}
modality. Cooper and Marzullo's algorithm for this problem
requires space exponential in size of the computation. We give a simple 
algorithm that requires only polynomial space.