2011isse Scc

8/14/2019 2011isse Scc

1/10

Noname manuscript No.(will be inserted by the editor)

Symbolic Computation of Strongly ConnectedComponents and Fair Cycles Using Saturation

Yang Zhao Gianfranco Ciardo

the date of receipt and acceptance should be inserted later

Abstract The computation of strongly connected com-ponents (SCCs) in discrete-state models is a criticalstep in formal verification of LTL and fair CTL prop-erties, but the potentially huge number of reachablestates and SCCs constitutes a formidable challenge. Weconsider the problem of computing the set of states inSCCs or terminal SCCs in an asynchronous system. Weemploy the idea ofsaturation, which has shown clear ad-vantages in symbolic state-space exploration [9,30], toimprove two previously proposed approaches. We usesaturation to speed up state exploration when comput-ing each SCC in the Xie-Beerel algorithm, and we com-

pute thetransitive closureof the transition relation us-ing a novel algorithm based on saturation. Furthermore,we show that the techniques we developed are also ap-plicable to the computation offair cycles. Experimen-tal results indicate that the improved algorithms usingsaturation achieve a substantial speedup over previousBFS algorithms. In particular, with the new transitiveclosure computation algorithm, up to 10150 SCCs canbe explored within a few seconds.

1 Introduction

Finding strongly connected components (SCCs) is a ba-sic problem in graph theory. For discrete-state models,some interesting properties, such as those expressible inLTL [19] and fair CTL [12], are correlated with the ex-istence of SCCs in the state-transition graph. The sameproblem is also central to the language emptiness checkfor-automata [17,19]. For large discrete-state models,it is impractical to find SCCs using explicit depth-first

Department of Computer Science and EngineeringUniversity of California, Riverside{zhaoy, ciardo}@cs.ucr.edu

state-space search [26] since its complexity is at least

linear in the size of the graph, motivating the study ofsymbolic SCC computation. In this paper, the objectiveis to build the set of states in SCCs.

The structure of SCCs in a graph is captured by itsquotient graph, obtained by collapsing each SCC into asingle node. This graph is acyclic, thus defines a partialorder on the SCCs. Terminal SCCs (or bottom SCCs)are nontrivial SCCs corresponding to leaf nodes in thequotient graph. For Markov chains [25] it is importantto classify the reachable states as recurrent (belongingto terminal SCCs) or transient(all other states), since

the probability that a Markov chain returns to a givenstate equals 1 iff that state is recurrent.

The complexity of these problems arises from twoaspects: having to explore a huge state space (almostalways the case in real-life problems) and having to dealwith a large number of SCCs or terminal SCCs (some-times the case in real-life problems). The former, knownas state explosion [12], is the main obstacle to formalverification due to the obvious burden it imposes oncomputational resources. Traditional BDD approachescope with this problem by employingimageandpreim-agecomputations for state-space exploration but, while

successful for fully synchronous systems [6], they donot work as well for asynchronous systems [9]. The lat-ter constitutes the bottleneck for one class of previouswork [28,29], which enumerates SCCs one by one. Sec-tion 2.3 analyzes this problem in more detail.

We address the computation of states in SCCs orterminal SCCs by improving two previous approaches:one proposed by Xie-Beerel (XB) [28,29] and one basedon computing the transitive closure (TC) of the transi-tion relation [17]. We apply the saturation algorithm [9]to both to cope with the cost of state-space exploration.Our previous work demonstrated clear advantages for

8/14/2019 2011isse Scc

2/10

2 Yang Zhao, Gianfranco Ciardo

saturation in state-space generation [9] (summarized inSection 2.2) and CTL model checking [10,30] over tra-ditional symbolic approaches. In this paper, we employsaturation for SCC analysis. Saturation greatly improvethe XB algorithm over its original version using BFS.With regards to a potentially huge number of SCCs, theTC algorithm has the advantage of exploring all SCCssymbolically instead of enumerating them one by one.However, as previously proposed, computing the TC of-ten requires large amount of runtime and memory [17],to the point that [22] claims that the TC algorithm isinfeasible for large examples. To disprove this myth,we propose a new saturation algorithm to compute theTC, making it a practical method of SCC computationfor complex systems. Furthermore, we present an algo-rithm to compute the recurrent states (i.e., states interminal SCCs) based on the TC.

Then, we consider fair cycle detection, a problem re-lated to SCC computation, but even more challenging.In Section 6, we discuss algorithms for detecting faircycles satisfying Streett fairness (strong fairness) [23].

The remainder of this paper is organized as fol-lows. Section 2 introduces the relevant background onthe data structures we use and saturation. Section 3presents a constrained saturation algorithm that limitsstate-space exploration to a given set of states. Section 4introduces an improved XB algorithm using saturation.Section 5 proposes our new algorithm to compute theTC using saturation and the corresponding algorithms

for SCC and terminal SCC computation. Section 6 dealswith the problem of finding fair cycles. Section 7 com-pares the performance of our algorithms and Lockstep.We discuss future work in the last section.

2 Preliminaries

Consider a discrete-state model (S, Sinit, E,N) where:

the potential state space Sis given by the productSL S1 of the finite local state spaces of Lsubmodels, so that each (global) state i is a tuple(iL, , i1), where ik Sk, for L k 1;

the set of initial states is Sinit S; the set of (asynchronous) events is E; the next-state function N : S 2S is described

in disjunctively partitioned form as N =

EN,where N(i) is the set of states that can be non-deterministically reached in one step when event

fires in state i.

We say that is enabled in state i ifN(i) =. Cor-respondingly,N1 andN1 denote the previous-statefunctions, e.g.,N1 (i) is the set of states that can reachiin one step by firing event .

In this paper, i,j, andk denote single states,X andYdenote sets of states, andN, possibly with a subscriptor superscript, denotes a next-state function.

Localityis a fundamental property enjoyed by asyn-chronous systems, expresses the fact that most eventsaffect only few systems components:

An event is independentof the kth submodel if itsenabling does not depend on ik and its firing doesnot change the value ofik.

If is not independent ofk th submodel, k is in thesupportof event , written as k supp().

LetTop() be the top index in supp(), andEk bethe set{ E :Top() = k}.

LetNk be the next-state function corresponding toall events inEk, i.e.,Nk =

Ek

N.

The problem of state-space generation refers to com-

puting the set Srch of states reachable from Sinit. Sec-tion 2.2 recalls our state-space generation algorithm,saturation, executed prior to SCC computation as a pre-processing step. Thus,Srch, the setsSk, and their sizesnk are assumed known in the following discussion, andwe letSk = {0,...,nk 1}without loss of generality.

2.1 Symbolic encoding of discrete-state systems

We employ multi-way decision diagrams (MDDs) [18]to encode discrete-state systems. MDDs extend binarydecision diagrams (BDDs) by allowing integer-valuedvariables, thus are suitable for discrete-state modelswith unknown (but hoped to be bounded) state spaces,such as Petri nets [21]. An MDD has two possible ter-minal nodes, 0 and 1, and a single root node.

A set of states is encoded with an L-level quasi-reducedMDD. Given a node a, its level is denoted witha.lvl where L a.lvl 0, a.lvl = 0 ifa is 0 or 1, anda.lvl = L if a is the root node. Ifa.lvl = k > 0, thena has nk outgoing edges, each labeled with a differentik Sk. The node pointed by the edge labeled with ikis denoted a[ik] and, if not 0, it must be at level k 1.

Turning to the encoding of the next-state functions,locality can be exploited to obtain a compact symbolic

expression. Since Ek does not affect iL, . . . , ik+1,N((iL, . . . , i1)) can be obtained as {(iL, . . . , ik+1)} N((ik, . . . , i1)). In other words, N only needs to beapplied to the lower k state components, thus, whena set of states is encoded with an MDD, firing N onthem only modifies the sub-MDDs rooted at level k ofthe MDD. The next-state function Nis encoded using a2L-level MDD, with levels orderedL, L,..., 1, 1, whereunprimed and primed levels describe from and tostates, respectively, and we let U(k) = U(k) = k. Weusequasi-identity-fully (QIF)reduced [27] MDDs to en-code next-state functions. This means that, for Ek,

8/14/2019 2011isse Scc

3/10

Symbolic Computation of Strongly Connected Components and Fair Cycles Using Saturation 3

N is encoded with a 2k-level MDD, so that the appli-cation ofN only needs to start at level Top().

We use lowercase letters to denote MDD nodes andrefer to an MDD by its root node, thus, MDD ameans the MDD rooted at node a. MDDa encodes asetB(a) Sa.lvl S 1 of (sub)-states, correspond-ing to the paths from a to 1. However, to simplify no-tation, we identify some global quantities with theirMDDs, e.g.,Nmeans either the next-state function orthe MDD encoding it, depending on the context.

Given a set of statesX =B(x) = S, the computa-tion ofN(X) can be implemented with the symbolicoperator RelProd, which takes an L-level MDD and a2L-level MDD in input and returns an L-level MDD:

N(X) = B(RelProd(x,N)).

In our pseudocode, we use the following functions:

(forward image) ImageF(x) RelProd(x,N),

(backward image) ImageB(x) RelProd(x,N1).

Using MDDs does not lead to higher efficiency thanBDDs, or even than explicit approaches (decision di-agrams are, after all, heuristics). Furthermore, as withBDDs, the chosenvariable ordergreatly affects the sizeand efficiency of MDDs, but choosing an optimal vari-able order is hard [4]. We use MDDs instead of BDDsin our work because it is easier to cope with models

whose local state spaces are not known a priori, such asPetri nets, by letting the size of MDD nodes grow onthe fly during state-space generation [9, 27].

2.2 State-space generation using saturation

All symbolic x state-space generation algorithms usesome variant of symbolic image computation. The sim-plest approach is a breadth-first search (BFS) directlyimplementing the definition ofSrch as the fixed pointSinit N(Sinit) N2(Sinit) . The forward reach-able states from a set of states Xcan be computed byReachF(X) =X N(X) N2(X) . Analogously,

we letReachB(X) = X N1(X) N2(X) .Saturation employs a different approach, recursively

computing local fixpointsand exploiting locality in thenext-state functions. The key idea is to fire events inan order consistent with their Top: we attempt firingevents in Ek on node a at level k only after having ex-haustively fired events in Eh, for all h < k, on nodes be-lowa, until no new states are found. Then, aissaturatedif it is a fixed point w.r.t. events independent of the lev-els above k:h, k h 1, Eh, B(a) N(B(a)).

Figure 1 shows the pseudocode of the saturation al-gorithm. Given a discrete-state model, NL, ...,N1 are

mdd SaturateF(mdd s)

1 if InCacheSaturateF(s, t) then return t; dont repeat work2 level k s.lvl;3 mdd t 0;4 foreachi Sk s.t. s[i]=0 do first, saturate nodes below

5 t[i] SaturateF(s[i]);6 endfor;

7 repeat keep firingNk until reaching convergence8 foreach i, i Sk s.t.Nk[i][i]=0 do9 t[i] Union(t[i], RelProdSat(t[i],Nk[i][i]));

10 endfor;

11 untilt does not change;

12 t InsertUT(t); Unique Table to avoid duplicate nodes13 CacheAddSaturateF(s, t); to avoid repeating work later14 returnt;

mdd RelProdSat(mdd s, r)

1 level k s.lvl;2 mdd t 0;3 ifs = 1 and r = 1 then return 1; endif; terminal case

4 if InCacheRelProdSat(s,r,t) then return t; endif;5 foreachi, i Sk s.t. r[i][i]=0 do6 t[i] Union(t[i], RelProdSat(s[i], r[i][i]));7 endfor;

8 t InsertUT(t); analogous to RelProd until here...9 t SaturateF(t); ...but now we saturatet before returning

10 CacheAddRelProdSat(s,r,t);11 returnt;

Fig. 1 The (forward) saturation algorithm.

globally available. The pseudocode shows a forward ex-ploration, as it uses the next-state functions, but it cannaturally be used for backward exploration by replac-

ing Nk with N

1

k . The input parameter s is the rootnode to be saturated, thus it is initially set to the rootof the MDD encoding Sinit. SaturateF saturates thenodes of MDD sin order, from the bottom level to thetop level. Unlike the traditional relational product op-eration, RelProdSatalways returns a saturated MDD.

2.3 Previous work

Symbolic SCC analysis has been widely explored [1316,22,24], and much effort has been spent on comput-ing theSCC hull. A family of SCC hull algorithms [24]employing BFS iteration is available. Although closely

related, there is crucial difference between SCC hullcomputation and our work, because an SCC hull con-tains not only states in nontrivial SCCs, but also stateson the paths between them, constituting a superset ofour desired result. In non-probabilistic model checking,computing the SCC hull aims at detecting the exis-tenceof reachable fair cycles, which is critical to verifyfair CTL, LTL and -automata properties. However,for Markov chains, the aim of SCC analysis is to collectthe states belonging to (trivial or nontrivial) terminalSCCs [2,11],. To this end, an SCC hull must be furtherdecomposed into states in an SCC and those not. To the

8/14/2019 2011isse Scc

4/10


best of our knowledge, no existing efficient symbolic al-gorithm is available for this task. Hence, SCC hull com-putation algorithms are notapplicable to our problemand we will not discuss them further. Instead, we reviewtwo categories of related previous work, which can com-pute the precise set of states in SCCs: the TC and theXB algorithms.

Hojati et al. [17] presented a symbolic algorithm totest -regular language containment by computing theTC N N2 N3 . Section 5 discusses the TC inmore detail. Matsunaga et al. [20] proposed a symbolicprocedure to compute the TC but the runtime is sopoor that building the TC has long been consideredimpractical for complex systems.

Xie et al. [29] proposed an algorithm, referred to asthe XB algorithm in this paper, combining explicit stateenumeration and symbolic state-space exploration. They

explicitly pick a state as a seed, compute the for-ward and backward reachable states from the seed, andfind the SCC containing this seed as the intersection ofthese two sets of states. Bloem et al. [3] presented animproved algorithm called Lockstep (Figure 2) which,given a seed, instead of computing the forward andbackward reachable states separately, it alternates BFSiterations between the two so that it can stop as soonas one of the two converges. This optimization achievesa O(n log n) complexity, compared to the O(n2) of theXB algorithm, computed in terms of number of imageand preimage computations, where n is the number of

reachable states. Our experiments show that Lockstepworks very well when the number of SCCs is manage-able. However, as the number of SCCs grows, the ex-haustive enumeration of SCCs becomes an formidableproblem for both the XB and the Lockstep algorithms.

Xie et al. [28] proposed a similar idea to computethe recurrent states in large Markov chains (XB TSCC

in Figure 2). From a randomly picked seed, if the set offorward reachable states B(f) is a subset of the set ofbackward reachable statesB(b), thenB(f) is a terminalSCC; otherwise, B(b) contains no terminal SCC andcan be eliminated from further consideration. Functions

ReachF andReachBwere implemented using BFS.Our work is the first to employ saturation in SCC

analysis. The two approaches we propose build upon theabove two previous approaches. For the XB algorithm,we replace BFS state-space exploration with saturation.For the TC approach, we propose a new algorithm tocompute TC using saturation.

3 Constrained saturation

The motivation behind the constrained saturation al-gorithm [30] is the computation of the CTL operator

mdd Lockstep(mdd p) initially, B(p) = Srch1 if (p= 0) then return 0;2 mdd s PickState(p); pick a seeds from B(p)3 mdd a 0; a accumulates the answer4 mdd f0; f accumulates the forward set from s

5 mdd b 0; b accumulates the backward set from s6 mdd c 0; c will be the SCC containings, if any7 mdd f Intersect(ImageF(s), p);8 mdd b Intersect(ImageB(s), p);9 whilef =0 and b =0 do

10 fUnion(f, f);11 b Union(b, b);12 f Diff(Intersect(ImageF(f), p), f);13 b Diff(Intersect(ImageB(b), p), b);14 endwhile;

15 if (f =0) then16 mdd v f; v remembers the set that converged first, f17 while Intersect(b, f)=0 do continue exploring backward18 b Diff(Intersect(ImageB(b), p), b);19 b Union(b, b);

20 endwhile;21 else

22 mdd v b; v remembers the set that converged first, b23 while Intersect(f, b)=0 do continue exploring forward24 f Diff(Intersect(ImageF(f), p), f);25 fUnion(f, f);26 endwhile;

27 endif;

28 ifIntersect(f, b)=0 then29 c Intersect(f, b); s belongs to the nontrivial SCCc30 endif;

31 a Union(c,Lockstep(Diff(v,c)),Lockstep(Diff(p,Union(v,s)))); divide and conquer in the remaining state space

32 returna;

mdd XB TSCC(mdd p) initially, B(p) = Srch1 mdd a 0; a collects the states in nontrivial terminal SCCs2 mdd s,f, b;

3 while (p=0) do4 s PickState(p); pick a seeds from B(p)5 fIntersect(ReachF(s), p);6 b Intersect(ReachB(s), p);7 ifDiff(f, b) = 0 then B(f) is a subset of B(b)8 a Union(a, f); add the new terminal SCC toa9 endif;

10 p Diff(p, b); dont consider the states in B(b) again11 endwhile;

12 returna;

Fig. 2 Lockstep for SCC computation and XB algorithm for

terminal SCC computation.

E[aUb], which returns the set of states backward reach-able from states satisfying property b through pathssatisfying property a. To constrain the state-space ex-ploration to a set of states a, a BFS approach cansimply intersect the newly reached states with a aftereach step. If we used a similar idea in ordinary satu-ration, however, intersection operations would have tobe executed after each event firing, destroying the ef-ficiency of saturation. Constrained saturation uses in-stead a check-and-fire strategy that constrains the

8/14/2019 2011isse Scc

5/10


mdd ConsSatB(mdd a, mdd s)

1 if InCacheConsSatB(a,s,t) then return t;2 level l s.lvl;3 mdd t 0;4 foreachi Sl s.t. s[i]=0 do first, saturate nodes below

5 ifa[i]=0 then6 t[i] ConsSatB(a[i], s[i]);7 else no new state in this sub-space sincea[i]=08 t[i] s[i];9 endif;

10 endfor;

11 repeat compute the local fixed point12 foreach i, i Sl s.t.N

1l

[i][i]=0 do13 ifa[i] = 0then execute only if the resulting states are in a14 t[i] Union(t[i], ConsRelProdB(a[i], t[i],N1

l [i][i]));

15 endif;

16 untilt does not change;

17 t InsertUT(t);18 CacheAddConsSatB(a,s,t);19 returnt;

mdd ConsRelProdB(mdd a, mdd s, mdd r)

1 ifs = 1 and r = 1 then return 1;2 if InCacheConsRelProdB(a,s,r,t) then return t;3 level l s.lvl;4 mdd t 0;5 foreachi, i Sl s.t. r[i][i]=0 do6 ifa[i] = 0then execute only if the resulting states are in a7 t[i] Union(t[i], ConsRelProdB(a[i], s[i], r[i][i]));8 endif;

9 endfor;

10 t ConsSatB(a, InsertUT(t)); saturatet before returning11 CacheAddConsRelProdB(a,s,r,t);12 returnt;

Fig. 3 Constrained (backward) saturation to compute EU.

exploration to a in each recursive call of the relationalproduct. The idea of constrained saturation is based onthe following observation:

B(t) = RelProd(s, r) B(a)

B(t[i]) =

iSl

(RelProd(s[i], r[i][i]) B(a[i])) ,

where t and s are l-level MDDs encoding sets of statesand r is a 2l-level MDD encoding a next-state func-tion. This can be considered an extension of the well-

known ITEoperator [5], from boolean to integer vari-ables. The overall process ofEUcomputation based onconstrained saturation is shown in Figure 3, where a

is the constraint and s is the set being saturated. Thekey differences from the saturation algorithm of [9] aremarked with a . The new states found by applyinga next-state function are guaranteed to satisfy a.

Neither saturation nor constrained saturation im-prove the theoretical computational complexity com-pared to the corresponding BFS algorithms. First, sat-uration could degrade to BFS if all events fall in EL.Second, both saturation and BFS may perform as bad

as enumerating states one by one in the worst case.However, [9, Theorem 1] demonstrates that saturationcan avoid building many MDD node that only appear inintermediate results, thus tends to result in much morecompact MDDs. Saturation is experimentally superiorto BFS for the local-synchronous-global-asynchronoussystems we studied. This is also reflected in the com-parison with Lockstep in the next section.

4 Using saturation in the XB algorithm

A natural improvement to the XB algorithm is to em-ploy saturation to explore the forward and backwardreachable states. Figure 4 shows the pseudocode of ouralgorithms: the two versions ofXBSatshown in the fig-ure compute the states in SCCs, or just in the terminal

SCCs, respectively. Unlike Lockstep, which uses the setthat converges first to bound the other, our algorithmcannot interleave the two computations or even predictwhich one will converge first, since saturation does notrun in a step-by-step manner. One obvious approach isthen to run a forward and a backward saturation andintersect the results. However, we experimentally foundthat we can do better by bounding one of the two satu-rations with the other. In Figure 4, for example, we al-ways bet on forward exploration and use it to boundbackward exploration (Line 7). This bet is of coursemost beneficial when (unconstrained) backward explo-ration is much slower than forward exploration. Thus,

there is a trade-off between using the slower BFS, whichhowever allows us to interleave the two explorations,and the faster saturation, which does not. Performanceis also affected by which seed is picked in each iterationand, for a fair comparison, we pick the same seed inboth algorithms at each iteration.

Both our new algorithm and Lockstep improve theoriginal XB algorithm, in different ways. Lockstep aimsat reducing the number of steps by carefully schedulingthe image and preimage computations, while our algo-rithm leverages event locality. Measuring complexity innumber of BFS steps,O(n log n) for Lockstep [3], is not

meaningful for saturation, which uses light-weight eventfirings instead of global image computations. Moreover,we argue that the number of steps is too rough a mea-sure of complexity because the cost of each symbolicstep varies greatly, exponentially with the number oflevels in the worst case. Instead, saturation aims at re-ducing the real cost in symbolic manipulation: as men-tion in Section 3, it avoids building many unnecessaryintermediate MDD nodes. Thus, while Lockstep ensuresa tight bound on the number of steps, saturation oftenexecutes fewer node operations, thus lower runtime andmemory requirements. Our experimental results show

8/14/2019 2011isse Scc

6/10


mdd XBSat(mdd p) initially, B(p) = Srch1 ifp = 0 then return 0; endif;2 mdd a 0;3 mdd s PickState(p); pick a seeds from B(p)4 mdd f Intersect(ImageF(s), p);

5 mdd b

Intersect(ImageB(s), p);6 mdd fIntersect(SaturateF(f), p);

forward reachable states from s in p

7 mdd b Intersect(ConsSatB(f, b), p); the intersection of backward and forward reachable states

8 ifb =0 then a b; endif; b = is a set of states in an SCC9 a Union(a, XBSat(Diff(f, b)), XBSat(Diff(p, f)));

divide and conquer in the remaining state space10 returna;

7 mdd b Intersect(SaturateB(b), p); backward reachable states from s in p

8 ifDiff(f, b) = 0 then a Union(a, f); endif; B(f) is a terminal SCC if B(f) B(b)

9 a Union(a, XBSat(Diff(p, b))); recursion in the remaining state space

10 returna;

Fig. 4 Improved XB algorithm using saturation (Lines 7 10compute SCCs, Lines 710 compute terminal SCCs).

that, for most models we studied, the improved XB al-gorithm using saturation outperforms Lockstep, some-times by orders of magnitude.

5 Computing the TC with saturation

We now define the forward and the backward TC, TandT1, of a discrete-state model.

Definition 1 The transitive closure T Srch Srchcontains all (i,j) such that there is a nontrivial (i.e.,positive length) path from i to j, denoted by i j.Analogously, we let (i,j) T1 iffj i.

T1 represents relations between pairs of states,and thus it can be encoded with a 2L-level MDD withthe same variable order with next-state functions. ik isplaced on level k (unprimed level) and jk on level k

(primed level), where U(k) = U(k) = k. As T andT1

are symmetric, we focus on the algorithm to computeT1. After T1 has been built, Tis obtained by simply

swapping the unprimed and primed levels in the MDDencoding T1, written as T= Invert(T1).We base our algorithm on the following observation:

(i,j) T1 k N1(i)j B(ConsSatB(Srch, s)),

where B(s) = {k}. Instead of running saturation on jfor each pair (i,j), we propose an algorithm that exe-cutes on the 2L-level MDD encoding N1. Line 1 infunctionSCC TCof Figure 5 computesT1 by callingTransClosSat, which runs bottom-up recursively. As forthe constrained saturation in Figure 3, this functionruns node-wise on primed level and fires lower level

events exhaustively until the local fixed point is ob-tained. This procedure ensures the following properties.

Property 1:Given ak-level MDDaand 2k-level MDDn, TransClosSat(a, n) returns a 2k-level MDD t s.t.

(i,j) B(n), k B(ConsSatB(a,j)) (i, k) B(t).Property 2: TransClosSat(Srch,N1)) = T1.

The top-level pseudocode of the SCC computationusing TC is shown as SCC TC in Figure 5. FunctionTCtoSCC extracts all states i such that (i, i) T1.Unlike SCC enumeration algorithms such as XB or Lock-step, a TC approach does not necessarily suffer from alarge number of SCCs. Nevertheless, due to the com-plexity of buildingT1, this approach had been consid-ered infeasible for complex systems. By employing sat-uration, instead, our algorithm to compute T1 com-pletes on some large models, such as the dining philoso-

pher problem with 1000 philosophers, while, for modelscontaining many SCCs, it may succeed where other al-gorithms have no hope. Thus, while the TC approachis not as robust as Lockstep, it can be used as an alter-native to it when Lockstep cannot enumerate all SCCs.

T1 can also be used to find recurrent states, i.e.,states in terminal SCCs. State j is in a terminal SCCif, for any statei,j i i j. Given two states i,j, let

j i mean j i and i j. We can encode this relationwith a 2L-level MDD, obtained as T1 \ T. The pseu-docode for this algorithm is shown as TSCC TCin Fig-ure 6. The set{(i,j) |ji}is encoded with a 2L-level

MDD r. Then, the set of states {j | i,ji}, whichdo notbelong to terminal SCCs, is computed by exis-tentially quantifying out the unprimed levels (Line 5),and stored in MDD nontscc. All other states are therecurrent states belonging to terminal SCCs.

To the best of our knowledge, this is the first TC-based algorithm for terminal SCC computation. Thisalgorithm is more costly in runtime and memory thanSCC computation because of the need to obtain the relation. However, by employing TransClosSat, itworks for most of the models we considered. Moreover,for models with a huge number of terminal SCCs, this

algorithm is, again, the only feasible approach.

6 Fair cycles

One application of the SCC computation is to check thelanguage emptiness of an -automaton. The languageof an -automaton is nonempty if there is a nontrivialcycle which satisfies a certain fairness condition, i.e.,a fair cycle. Thus, it is necessary to extend the SCCcomputation to finding fair cycles. Two widely usedfairness conditions are Buchi fairness (weak fairness)and Streett fairness (strong fairness) [12].

8/14/2019 2011isse Scc

7/10


mdd SCC TC(N1)

1 mddT1 TransClosSat(Srch,N1);2 mdd SCC TCtoSCC(T1);3 returnS CC;

mdd TransClosSat(mdd a, mdd n)

1 ifn = 1 then return 1; endif;2 if InCacheTransClosSat(a,n,t) then return t; endif;3 level k n.lvl; L U(k) 14 mdd t 0;5 mdd r N1

U(k);

6 foreachi, j Sk s.t. n[i][j]=0 do7 ifa[j]=0 then first, saturate nodes below8 t[i][j] TransClosSat(a[j], n[i][j]);9 else no new path in this sub-space sincea[i]=0

10 t[i][j] n[i][j];11 endif;

12 endfor;

13 foreachi SU(k) s.t. n[i]=0 do14 repeat compute the local fixed point

15 foreach j,j

SU(k) s.t. n[i][j] = 0r[j][j

] = 0a[j

] = 0do r is applied to the primed levels ofn

16 t[i][j]Union(t[i][j],TCRelProdSat(a[j],t[i][j],r[j][j]));17 endfor;

18 until t does not change;

19 endfor;

20 t InsertUT(t);21 CacheAddTransClosSat(a,n,t);22 returnt; t is a2L-level MDD encoding TransClosSat(a, n)

mdd TCRelProdSat(mdd a, mdd n,mdd r)

1 ifn = 1 and r = 1 then return 1; endif;2 if InCacheTCRelProdSat(a,n,r,t) then return t; endif;3 level k n.lvl; L U(k) 14 mdd t 0;

5 foreachi SU(k) s.t. n[i]=0 do6 foreach j,j SU(k) s.t. n[i][j] = 0r[j][j

] = 0a[j] = 0do r is applied on primed levels in n

7 t[i][j]Union(t[i][j],TCRelProdSat(a[j],n[i][j],r[j][j]));8 endfor;

9 endfor;

10 t TransClosSat(a,InsertUT(t)); return a saturated result11 CacheAddTCRelProdSat(a,n,r,t);12 returnt;

mdd TCtoSCC(mdd n)

1 ifn = 1 return 1; endif;2 if InCacheTCtoSCC(n, t) then return t; endif;3 level k n.lvl; L U(k) 14 mdd t 0;

5 foreachi SU(k) s.t. n[i][i]=0 do6 t[i] TCtoSCC(n[i][i]);7 endfor;

8 t InsertUT(t);9 CacheAddTCtoSCC(n, t);

10 returnt; t is an L-level MDD enconding{i: (i, i) B(n)

Fig. 5 Building the TC using saturation.

Strong fairness is specified with a set of pairs ofsets{(R1, C1), . . . , (Rn, Cn)} and a cycle satisfies it iff,for each (Ri, Ci), either no state ofRi is in the cycleor some state of Ci is in the cycle. Weak fairness isspecified with a set of sets of states {F1, F2, . . . , Fn}.

mdd TSCC TC(N1)

1 mddT1 TransClosSat(N1);2 mddT Inverse(T1); swap adjacent levelsk andk

3 mdd scc TCtoSCC(T1);4 mdd r Diff(T1, T);

5 mdd nontscc QuantUnpr(r

); quantify out unprimed levels in r,nontsccis an L-level MDD

6 mdd recurrent Diff(scc, nontscc);7 return recurrent;

Fig. 6 Computing recurrent states using TC.

Its semantics is expressed by the special case of strongfairness where, in each pair, Ri = Srch and Ci = Fi,thus we focus on strong fairness.

Lockstep is also able to find strongly fair cycles [3],but might suffer from SCC refinement [3, Figure 4].This occurs when an SCC intersects a Ri but not Ci.Then, we need to to filter out all states in Ri and runLockstep on the remaining states in this SCC. This pro-cess may enumerate all states in the worst case, as withSCC enumeration. Here, we present a TC approach thatavoids enumeration. To the best of our knowledge, thisis the first TC approach for fair cycle detection. Thefollowing defines theconstrained TC.

Definition 2 Given a set of states X, the constrainedbackward TC is T1X =TransClosSat(X,N

1).

T1X specifies the relation between two statesi andj, such that (i,j) T1X j t1 t2 . . . i and

t1, t2, . . . , i X. Thus, the set of states belonging tosome (strongly) fair cycle is given by:

m=1,...,n

TCtoSCC(T1Srch\Rm)

{i | cm Cm, (T(cm, i) T1(cm, i))}

,

If (i,i) T1Srch\Rm, there is a nontrivial path from i to

i that avoids Rm. Thus, TCtoSCC(T1Srch\Rm

) returnsthe states in cycles that contain no state in Rm andsatisfy strong fairness. If (i,cm) (T(cm,i)T1(cm,i)),

i belongs to a cycle which contains states in cm. Thesubformula in the second line corresponds to the statesin a cycle containing at least one state inCm, satisfyingstrong fairness.

The pseudocode in Figure 7 computes the above for-mula. For each (Rm, Cm),c encodes the states in cyclesthat do not intersectRm,d encodes the states in cyclesthat intersect Cm, and Cross(Cm, Srch) returns a 2L-level MDD encoding the cross-product ofCm andSrch .The cost mainly lies in computing the intersection ofT1 andT, which is similar to computing the relation. Moreover, the complexity grows linearly with thesize n of the fairness condition.

8/14/2019 2011isse Scc

8/10


mdd FairSCC TC(Srch,N1, {(R1, C1), . . . , (Rn, Cn)})

1 mddT1 TransClosSat(Srch,N1);2 mddT Inverse(T1);3 mdd s Srch;4 foreachm = 1, , n do

5 mdd c TCtoSCC(TransClosSat(Diff(Srch, Rm),N

1));6 mdd d Intersect(T1, T);7 d QuantUnpr(Intersect(d, Cross(Cm, Srch)));

Cross(Cm,Srch) encodes{(cm,i) : cm Rmi Srch}8 s Intersect(s, Union(c, d));9 endfor;

10 returns;

Fig. 7 Computing fair cycles using TC.

7 Experimental results

We implemented our algorithms in SmArT [8] and reportexperimental results running on an Intel Xeon 3.0Ghzworkstation with 3GB RAM under SuSE Linux 9.1.The models, described as Petri nets and translated intothe input language ofSmArT, include the closed queuenetwork (cqn) of [29], two implementations of arbiters(arbiter1, arbiter2) [1], one which guarantees fairnessand the other which does not, the queen placementproblem (queens), the dining philosopher problem (phil),and the leader selection protocol (leader) [7]. The sizefor each model is controlled by a parameter N. Thenumber of SCCs (terminal SCCs) and states in SCCs(terminal SCCs) for each model is listed in columnSCC count (TSCC count) and column SCC states(TSCC states), respectively. We set and upper bound

of 2hr for runtime and 1GB for the unique table (usedto canonically store the MDD nodes). The main met-rics of our comparison are runtime and peak memoryconsumption (for unique table plus operation cache, re-quired for efficient dynamic programming implementa-tion of MDD operation), which are measured in secondsand megabytes, respectively.

The top part of Table 1 compares three algorithmsfor SCC computation: the TC algorithm (column TC)of Section 5, the improved XB algorithm (column XB-SAT) of Section 4, and Lockstep (column Lockstep).We can see that the improved XB algorithm using satu-

ration is better than Lockstep for most models, in bothruntime and memory. Compared with the SCC enu-meration algorithms, the TC algorithm is often moreexpensive but, for queens and arbiter2, it completeswithin the time limit while the other two algorithmsfail. Forarbiter2, our TC algorithm explores over 10

150

SCCs in a few seconds, while it is obviously not feasi-ble to exhaustively enumerate all SCCs in reasonabletime. To the best of our knowledge, this is the best re-sult of SCC computation reported, confirming the mainadvantage of the TC algorithm: its insensitivity to thenumber of SCCs. With the help of our new algorithm,

the TC can be built for some large systems, such as thedining philosopher problem with 1000 philosophers.

The bottom part of Table 1 compares three algo-rithms for terminal SCC computation: XBSat(columnXBSat) presented in Sections 4 , TSCC TC(columnTC) presented in Sections 5, and the BFS XB al-gorithmXB TSCC(column XBBFS) shown in Fig-ure 2. The basic trends are similar to those for SCCcomputation: algorithmXBSatworks consistently bet-ter than the traditional method, while TSCC TC isless efficient for most models. In the framework of theXB algorithm, computing terminal SCCs is faster thancomputing SCC because a larger set of states is prunedat each recursion. On the contrary, TSCC TC is moreexpensive than SCC TC due to the computation ofthe relation. As a consequence, TSCC TC sufferseven more from large memory and runtime requirement.

Nevertheless, for models with large numbers of termi-nal SCCs, such as queens, TSCC TC outperforms theBFS XB algorithm.

Some conclusions can be drawn from the above re-sults and discussion. First, saturation is effective inspeeding up SCC and terminal SCC computation withinthe framework of the XB algorithm. Second, our newsaturation algorithm makes TC computation feasiblefor some complex models containing up to 10150 states.Third, SCC computation based on TC is superior toSCC enumeration algorithms, which find SCCs one-by-one, for models with huge numbers of SCCs.

Although the TC approach is not as robust as Lock-step, especially when the number of SCCs in the modelis manageable, we argue that it should be consideredas a reasonable alternative worth of further research.Given a new model with an unknown number of existingSCCs, employing both of these approaches at the sametime will be ideal. Current trend of multi-core comput-ers provide a possible means of parallelizing these twoalgorithms. Some of the common data structures, likeMDDs encoding the state space and next-state func-tions, could then even be shared.

8 Conclusion and future work

We focused on improving two previous approaches forSCC computation, the Xie-Beerel (XB) and the transi-tive closure (TC) algorithms, using saturation. For theasynchronous models we study, the improved XB al-gorithm using saturation achieves a clear speedup andour new algorithm to compute TC using saturation isexperimentally shown to be capable of handling modelswith up to 10150 of SCCs. We argue that the TC-basedapproach is worth further research because of its abilityto deal with models having huge numbers of SCCs.

8/14/2019 2011isse Scc

9/10


Results for the SCC computation

ModelSCC count SCC states

TC XBSat Lockstepname N mem time mem time mem time

cqn

10 11 2.09e+10 34.2 13.6 3.4

8/14/2019 2011isse Scc

10/10


5. Randy E. Bryant. Graph-based algorithms for booleanfunction manipulation. IEEE Transactions on Computers,35(8):677691, August 1986.

6. J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill,and L. J. Hwang. Symbolic model checking: 1020 statesand beyond. Information and Computation, 98:142170,1992.

7. Gianfranco Ciardo et al. SMART: Stochas-tic Mo del checking Analyzer for Reliabil-ity and Timing, User Manual. Available athttp://www.cs.ucr.edu/ciardo/SMART/.

8. Gianfranco Ciardo, Robert L. Jones, Andrew S. Miner,and Radu Siminiceanu. Logical and stochastic modelingwith SMART. Perf. Eval., 63:578608, 2006.

9. Gianfranco Ciardo, Robert Marmorstein, and Radu Si-miniceanu. The saturation algorithm for symbolic statespace exploration. Software Tools for Technology Transfer,8(1):425, February 2006.

10. Gianfranco Ciardo and Radu Siminiceanu. Structuralsymbolic CTL model checking of asynchronous sys-tems. In Warren Hunt, Jr. and Fabio Somenzi, editors,

Proc. CAV, LNCS 2725, pages 4053, Boulder, CO, USA,July 2003. Springer-Verlag.

11. Frank Ciesinski, Christel Baier, Marcus Grosser, andJoachim Klein. Reduction techniques for model check-ing Markov decision processes. In Proceedings of the 2008Fifth International Conference on Quantitative Evaluation

of Systems, pages 4554, Washington, DC, USA, 2008.IEEE Computer Society.

12. Edmund M. Clarke, Orna Grumberg, and Doron A.Peled. Model Checking. MIT Press, 1999.

13. E. Allen Emerson and Chin-Laung Lei. Efficient modelchecking in fragments of the propositional mu-Calculus).In Proceedings, Symposium on Logic in Computer Science,16-18 June 1986, Cambridge, Massachusetts, USA, pages267278. IEEE Computer Society, 1986.

14. Kathi Fisler, Ranan Fraer, Gila Kamhi, Moshe Y. Vardi,and Zijiang Yang. Is there a best symbolic cycle-detectionalgorithm? In Proceedings of the 7th International Con-

ference on Tools and Algorithms for the Construction andAnalysis of Systems, TACAS 2001, pages 420434, Lon-don, UK, 2001. Springer-Verlag.

15. G. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Marko-vian analysis of large finite state machines. IEEE Trans.CAD of Integr. Circ. and Syst., 15(12):14791493, Decem-ber 1996.

16. R. H. Hardin, R. P. Kurshan, S. K. Shukla, and M. Y.Vardi. A new heuristic for bad cycle detection using bdds.Formal Methods in System Design, 18(2):131140, 2001.

17. Ramin Hojati, Herve J. Touati, Robert P. Kurshan, andRobert K. Brayton. Efficient -regular language contain-ment. In CAV, pages 396409, 1992.

18. Timothy Kam, Tiziano Villa, Robert K. Brayton, andAlberto Sangiovanni-Vincentelli. Multi-valued decisiondiagrams: theory and applications. Multiple-Valued Logic,4(12):962, 1998.

19. Yonit Kesten, Amir Pnueli, and Li-on Raviv. Algorith-mic verification of linear temporal logic specifications.In ICALP 98: Proceedings of the 25th International Col-loquium on Automata, Languages and Programming, pages116, London, UK, 1998. Springer-Verlag.

20. Y. Matsunaga, P.C. McGeer, and R.K. Brayton. On com-puting the transitive closure of a state transition relation.In Design Automation, 1993. 30th Conference on, pages260265, June 1993.

21. Tadao Murata. Petri nets: properties, analysis and ap-plications. Proc. of the IEEE, 77(4):541579, April 1989.

22. Kavita Ravi, Roderick Bloem, and Fabio Somenzi. Acomparative study of symbolic algorithms for the com-putation of fair cycles. In FMCAD 00: Proceedingsof the Third International Conference on Formal Methods

in Computer-Aided Design, pages 143160, London, UK,2000. Springer-Verlag.

23. Shmuel Safra and Moshe Y. Vardi. On omega-automataand temporal logic. In Proceedings of the Twenty-First An-nual ACM Symposium on Theory of Computing, 15-17 May

1989, Seattle, Washington, USA, pages 127137. ACM,1989.

24. Fabio Somenzi, Kavita Ravi, and Roderick Bloem. Anal-ysis of symbolic SCC hull algorithms. In FMCAD 02:Proceedings of the 4th International Conference on Formal

Methods in Computer-Aided Design, pages 88105, Lon-don, UK, 2002. Springer-Verlag.

25. William J. Stewart. Introduction to the Numerical Solutionof Markov Chains. Princeton University Press, 1994.

26. Robert Tarjan. Depth-first search and linear graph algo-rithms. In Proceedings of the 12th Annual Symposium onSwitching and Automata Theory (swat 1971), pages 114

121, Washington, DC, USA, 1971. IEEE Computer Soci-ety.

27. Min Wan and Gianfranco Ciardo. Symbolic state-spacegeneration of asynchronous systems using extensible de-cision diagrams. In M. Nielsen et al., editors, Proc.35th Int. Conf. Current Trends in Theory and Practice ofComputer Science (SOFSEM), LNCS 5404, pages 582594, Spindleruv Mlyn, Czech Republic, February 2009.Springer-Verlag.

28. Aiguo Xie and Peter A. Beerel. Efficient state classifica-tion of finite-state Markov chains. IEEE Trans. on CAD ofIntegrated Circuits and Systems, 17(12):13341339, 1998.

29. Aiguo Xie and Peter A. Beerel. Implicit enumerationof strongly connected components and an application toformal verification. IEEE Trans. on CAD of Integrated

Circuits and Systems, 19(10):12251230, 2000.30. Yang Zhao and Gianfranco Ciardo. Symbolic CTL modelchecking of asynchronous systems using constrained satu-ration. In Zhiming Liu and Anders P. Ravn, editors, Proc.7th International Symposium on Automated Technology forVerification and Analysis (ATVA), LNCS 5799, pages 368381, Macao SAR, China, October 2009. Springer-Verlag.

Documents

2011isse Scc